Question

Prove that the complement of a planar graph on at least 11 vertices
is not a planar graph.

Answer 1

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: