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
  • 4
    $\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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .