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?
Best Answer
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$.