11
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ Maybe using Kuratowki's theorem. $\endgroup$ – Josué Tonelli-Cueto Apr 6 '12 at 10:54
  • 2
    $\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 '12 at 10:55
12
$\begingroup$

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

$\endgroup$
  • $\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 '12 at 1:49
  • 1
    $\begingroup$ I've had this doubt, could it be that both $G \text{ and } \overline G$ are not planar? $\endgroup$ – YoTengoUnLCD Sep 13 '15 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 '16 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.