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.