Graph Theory: A has 15 edges, Ā has 13 edges, how many vertices does A have?

**yvonnehr** · June 22nd 2008, 08:55 PM

Discrete Math: Graph Theory #54.
If A is a simple graph with 15 edges, and Ā has 13 edges, how many vertices does A have?

Can anyone give me the answer and how to arrive at it?

Thanks a bunch,
Yvonne

**kalagota** · June 22nd 2008, 09:40 PM

Originally Posted by yvonnehr

Discrete Math: Graph Theory #54.
If A is a simple graph with 15 edges, and Ā has 13 edges, how many vertices does A have?

Can anyone give me the answer and how to arrive at it?

Thanks a bunch,
Yvonne

do you know this statement?

Let $\overline{G}$ be the complementary graph of $G$ . Then
$|E(\overline{G})| + |E(G)| = \left({\begin{array}{c} |V(G)| \\ 2 \end{array}}\right)$

**yvonnehr** · June 22nd 2008, 09:48 PM

Originally Posted by kalagota

do you know this statement?

Let $\overline{G}$ be the complementary graph of $G$ . Then
$|E(\overline{G})| + |E(G)| = \left({\begin{array}{c} |V(G)| \\ 2 \end{array}}\right)$

I don't believe I have seen this. Is this related or some rendition of the Handshaking Theorem?
-Ivy

**kalagota** · June 22nd 2008, 09:59 PM

i dont think so.. we discussed this as a remark in graph operations..

**yvonnehr** · June 22nd 2008, 10:05 PM

Originally Posted by kalagota

do you know this statement?

Let $\overline{G}$ be the complementary graph of $G$ . Then
$|E(\overline{G})| + |E(G)| = \left({\begin{array}{c} |V(G)| \\ 2 \end{array}}\right)$

Tell me I am reading this right.

The sum of the cardinality of (edges) G and G-compliment equals to the cardinality of (vertices) G.

Sorry if I am not getting this correctly. It is very late for me. :-) You know how it goes.

**kalagota** · June 22nd 2008, 10:20 PM

Originally Posted by yvonnehr

Tell me I am reading this right.

The sum of the cardinality of (edges) G and G-compliment equals to the cardinality of (vertices) G.

Sorry if I am not getting this correctly. It is very late for me. :-) You know how it goes.

... cardinality of (vertices) G taken 2..

EDIT: that is the usual combination formula..

Thread: Graph Theory: A has 15 edges, Ā has 13 edges, how many vertices does A have?

LinkBack

Thread Tools

Display

Graph Theory: A has 15 edges, Ā has 13 edges, how many vertices does A have?

Equation -> Handshaking Theorem?

Reading new equation.

Similar Math Help Forum Discussions

Graph theory : coloring edges

Deriving the formula for the edges of an m-Partite graph over n vertices.

Vertices and Edges

Edges and vertices of a solid

Eulerian graph with even vertices and odd edges

Search Tags