5
$\begingroup$

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?

  • 0
    In fact, it is possible that both $G$ and $G^\complement$ are non-planar. If $G=K_5, G^\complement=K_6$, which includes $K_{3,3}$2012-11-14

1 Answers 1

8

There is no need to apply Kuratowski's theorem here. We will use the fact that a planar graph cannot have too many edges.

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.