Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|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
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|cite|improve this answer
Thanks very much for the explanation! – User3419 Apr 28 '11 at 11:31

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.