Sign up ×
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.

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

1 Answer 1

up vote 6 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 at 20:13

Your Answer


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.