1
$\begingroup$

Possible Duplicate:
How to prove that a simple graph having 11 or more vertices or its complement is not planar?

I need to prove some graph problem.

Let G be planar graph with more than 10 vertices. I need to prove the its complement graph G' is not planar.

  • 0
    Thanks, It's exacly the same :D2012-09-26

2 Answers 2

3

If n ≥ 3 then e ≤ 3n − 6; and If n ≥ 3 and there are no cycles of length 3, then e ≤ 2n − 4. you can use this too to prove by contradiction....

0

Hint: Try to show that $G'$ contains a full subgraph of 5 vertices $K_5$ or the full bipartite graph $K_{3,3}$.