Complement graph not planar

Nov 2013
17
0
England
Hello,


I have the following question:
Let G be a simple graph with 2 connected components. Each component has at least 3 edges.


Prove that G's complement graph is not planar.


Now what I thought would make sense is that all the edges in the complement graph cross each other so it can't be planar, and also tried to solve in with Euler chararcteristic, unsuccessfuly.


Any help is appriciated.
 

emakarov

MHF Hall of Honor
Oct 2009
5,577
2,017
Since each component has at least 3 edges, it has at least 3 vertices. Therefore, the complement contains K3,3, doesn't it?