Take the 2-minute tour ×

Here is a sample problem I need to know how to solve:

The complementary graph $\overline{G}$ of a simple graph $G$ has the same vertices as $G$. Two vertices are adjacent in $\overline{G}$ if and only if they are not adjacent in $G$. If $G$ has 15 edges and $\overline{G}$ has 13 edges, how many vertices does $G$ have?

What I can explain myself is, that the sum of the degrees of all vertices of $G$ and $\overline{G}$ are 30 and 26 respectively. What I am not sure about is whether it follows from the above that the union of the two graphs is a complete graph with a sum of the degrees of its vertices equal to 56.

Could you help me out here, please?

share|improve this question
Hint: The total number of possible edges is $\binom{V}{2}$ where $V$ is the number of vertices. –  Grumpy Parsnip Apr 28 '11 at 1:28
By definition, the union of $G$ and $\bar G$ is the complete graph in $n$ vertices, if $G$ has $n$ vertices. –  lhf Apr 28 '11 at 1:47
@Jim Conant and @lhf: Thank you! –  User3419 Apr 28 '11 at 11:31

1 Answer 1

up vote 3 down vote accepted

Suppose $G$ is a graph of order $n$. Since $G$ is simple, you have $|E(G)|+|E(\overline{G})|=|E(K_n)|$, that is, $|E(K_n)|=28$. This amounts to solving $\binom{n}{2}=28$, and trying the first few integers shows $n=8$.

share|improve this answer
Thanks very much for the explanation! –  User3419 Apr 28 '11 at 11:31

Your Answer


