It is an exercise on a book again. If a simple graph $G$ has 11 or more vertices,then either G or its complement $\overline { G } $ is not planar.

How to begin with this? Induction?

Thanks for your help!

  • $\begingroup$ Maybe using Kuratowki's theorem. $\endgroup$ Apr 6, 2012 at 10:54
  • 3
    $\begingroup$ Or maybe Euler's formula. What is the maximum number of edges that a simple planar graph with 11 vertices can have? $\endgroup$
    – Peter Shor
    Apr 6, 2012 at 10:55

1 Answer 1


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

  • $\begingroup$ Oh,the book I am reading now doesn't have this formula m≤3n−6 ... Now it seems not to be a good book. $\endgroup$
    – tamlok
    Apr 7, 2012 at 1:49
  • 1
    $\begingroup$ I've had this doubt, could it be that both $G \text{ and } \overline G$ are not planar? $\endgroup$ Sep 13, 2015 at 20:13
  • $\begingroup$ @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. $\endgroup$
    – JMoravitz
    May 25, 2016 at 17:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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