# Prove nonplanarity of a graph

So I'm working to prove that any graph $G=(V,E)$ with $|V|\geq11$ will either be nonplanar itself, or its complement $G^\complement$ will be nonplanar.

My text says that to prove nonplanarity, one must show that the graph has a subgraph that is homeomorphic to either $K_5$ or $K_{3,3}$.

My question is: Would it be suffice to prove that it is impossible for both $G$ and $G^\complement$ to be nonplanar?

-
Yup, if you can prove that it's impossible for both $G$ and $G^\mathrm{c}$ to be planar then you're done. – EuYu Nov 14 '12 at 0:13
@EuYu: The question that you're answering affirmatively says "nonplanar", not "planar"- – joriki Nov 14 '12 at 0:23
My mistake. It's not sufficient to prove that both $G$ and $G^\mathrm{c}$ are non-planar. – EuYu Nov 14 '12 at 0:29
Thank you both. – connorbode Nov 14 '12 at 0:35
In fact it is possible for both $G$ and $G^c$ to be non-planar and $G$ to have arbitrarily many vertices. – Max Nov 14 '12 at 1:13

Lemma: If $G(V,\ E)$ satisfies $|E| > 3|V| - 6$ then $G$ is non-planar.
Now consider the edges of the graph and the complement $\overline{G}(V,\ E')$. The edges satisfy $$|E| + |E'| = \binom{|V|}{2} = \frac{|V|^2 - |V|}{2}$$ Therefore at least one of the two graphs must have at least $\frac{|V|^2 - |V|}{4}$ edges. Looking at the inequality $$\frac{|V|^2 - |V|}{4} > 3|V| - 6 \implies |V|^2 - 13|V| + 24 > 0$$ This inequality is satisfied for $|V| \ge 11$ and hence the result.
As a note of interest, it has been shown (through case by case analysis) that we can lower the number of vertices to $9$ while retaining this property. $9$ is the smallest number of vertices such that either $G$ or $\overline{G}$ is non-planar.