11
$\begingroup$

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!

  • 2
    Or maybe Euler's formula. What is the maximum number of edges that a simple planar graph with 11 vertices can have?2012-04-06

1 Answers 1

12

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

  • 0
    @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](http://math.stackexchange.com/questions/280034/draw-a-non-planar-graph-whose-complement-is-a-non-planar-graph).2016-05-25