146k views
5 votes
Prove that the complement of a planar graph on at least 11 vertices
is not a planar graph.

1 Answer

0 votes

Answer:18

It follows from the Euler's formula that a simple planar graph G with m edges and n≥3 vertices must satisfy (see here)

m≤3n−6.(1)

For a graph G with m edges and n vertices, its complement G¯¯¯¯ has n(n−1)2−m edges. Therefore, if G¯¯¯¯ is also planar, by (1) we have

n(n−1)2−m≤3n−6.(2)

Adding (1) and (2), we obtain

n(n−1)2≤6n−12,

which implies that n≤10.

Explanation:

User Doug Hudgeon
by
8.5k points

No related questions found

Welcome to QAmmunity.org, where you can ask questions and receive answers from other members of our community.

9.4m questions

12.2m answers

Categories