Past exam of the mathematics course of the University of Cambridge / 2020 / ii / Paper 1 / 17G / a / Solution

Let $G$ have $n$ vertices and $e$ edges. Its complement graph $\overline{G}$ hasedges. If both graphs were planar, the planar graph edge bound would giveEquivalently, $n^2-13n+24\le 0$, whose larger root is $(13+\sqrt{73})/2<11$. Thus an integer $n\ge 11$ is impossible, proving that

Now suppose that $G$ and $\overline{G}$ are both bipartite. In a bipartition $V(G)=A\bigsqcup B$, every pair within $A$ and every pair within $B$ is adjacent in $\overline{G}$. Since a bipartite graph contains no triangle, $|A|,|B|\le 2$, and hence $|V(G)|\le 4$. Equality is attained by the path $P_4$, whose complement is again a copy of $P_4$. Therefore the maximum order is