Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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
1  
@EuYu: The question that you're answering affirmatively says "nonplanar", not "planar"- –  joriki Nov 14 '12 at 0:23
1  
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
show 1 more comment

1 Answer

up vote 7 down vote accepted

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.