How to prove that a simple graph having 11 or more vertices or its complement is not planar?

Question

It is an exercise on a book again.If a simple graph G has 11 or more vertices,then either G or is complement $\bar { G } $ is not planar. How to begin with this?Induction? Thanks for your help!

Answer 1

It follows from the Euler's formula that a simple planar graph $G$ with $m$ edges and $n\geq 3$ vertices must satisfy (see here) $$\tag{1}m\leq 3n-6.$$ For a graph $G$ with $m$ edges and $n$ vertices, its complement $\overline{G}$ has $\displaystyle\frac{n(n-1)}{2}-m$ edges. Therefore, if $\overline{G}$ is also planar, by $(1)$ we have $$\tag{2}\frac{n(n-1)}{2}-m\leq 3n-6.$$ Adding $(1)$ and $(2)$, we obtain $$\frac{n(n-1)}{2}\leq 6n-12,$$ which implies that $n\leq 10$.