Exercise 1.2.11
These are the solutions to the exercises of the book Graph Theory with Applications by J. A. Bondy and U. S. R. Murty.
(a) The graph K_n^c is called the empty graph and it has n vertices and no edges.
The graph K_{n,m}^c is the union of two complete graphs K_n and K_m.
(b) Let G\simeq G^c. Therefore there exists a bijection \theta : V(G)\rightarrow V(G^c) such that uv\in E(G)\iff \theta(u)\theta(v)\in E(G^c).
Therefore there exists a bijection \theta : V(G)\rightarrow V(G^c) such that uv\in E(G)\iff \theta(u)\theta(v)\notin E(G).
Hence there exists a one-to-one correspondence between the edges and the non-edges of G.
\begin{aligned}\therefore \lvert E(G) \rvert &=\lvert E(G^c) \rvert\\\epsilon &= \binom{\nu}{2}-\epsilon\\2\epsilon&=\binom{\nu}{2}\\2\epsilon&=\frac{\nu (\nu-1)}{2}\\\epsilon&=\frac{\nu (\nu-1)}{4}\end{aligned}Since \epsilon is a positive integer, either one of the following cases is true:
Case 1: 4 divides \nu
Case 2: 4 divides \nu-1
Case 3: 2 divides both \nu and \nu-1.
Case 3 is impossible, hence the result follows. \square
The solutions of all the exercises of “Graph Theory with Applications” by J. A. Bondy and U. S. R. Murty, are available for download as a pdf file! Click the button below.