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.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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!

share|cite|improve this question
    
Maybe using Kuratowki's theorem. – Josué Tonelli-Cueto Apr 6 '12 at 10:54
2  
Or maybe Euler's formula. What is the maximum number of edges that a simple planar graph with 11 vertices can have? – Peter Shor Apr 6 '12 at 10:55
up vote 8 down vote accepted

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$.

share|cite|improve this answer
    
Oh,the book I am reading now doesn't have this formula m≤3n−6 ... Now it seems not to be a good book. – tamlok Apr 7 '12 at 1:49
    
I've had this doubt, could it be that both $G \text{ and } \overline G$ are not planar? – YoTengoUnLCD Sep 13 '15 at 20:13
    
@YoTengoUnLCD Of course. What this proved was that at least one of $G$ and $\overline{G}$ must be nonplanar. If you want specific constructions of graphs who are nonplanar whose complements are also nonplanar, see for example this question. – JMoravitz May 25 at 17:46

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.