Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question

marked as duplicate by Paul, Douglas S. Stones, draks ..., Chris Eagle, MJD Sep 27 '12 at 6:20

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

see here:… – Paul Sep 26 '12 at 12:13
Thanks, It's exacly the same :D – Some1Pr0 Sep 26 '12 at 12:38

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

share|cite|improve this answer

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

share|cite|improve this answer

Not the answer you're looking for? Browse other questions tagged or ask your own question.