Planar Graphs

Euler's V − E + F = 2, the edge bound, and non-planar K₅ / K₃,₃.

The idea

A graph is planar if it can be drawn in the plane with no two edges crossing. In such a drawing, write $V$ for the number of vertices, $E$ for the number of edges, and $F$ for the number of faces — the connected regions the drawing cuts the plane into, counting the one unbounded outer region.

Theorem (Euler's formula).

For every connected graph drawn in the plane with no two edges crossing, $V - E + F = 2.$

Planarity is a property of the graph, not of any one picture: a graph drawn with crossings may still be planar, because a different drawing of the same graph may avoid them. So proving a graph planar takes one good drawing, while proving it non-planar requires ruling out every possible drawing.

Euler's formula supplies that argument. The formula holds for every crossing-free drawing, whatever its shape and wherever its vertices were placed, so its consequences constrain every planar drawing at once.

Corollary (Edge bound).

A simple planar graph with $V \ge 3$ vertices has $E \le 3V - 6$ edges.

A graph that violates the bound therefore admits no planar drawing at all.

Ways to work on it

• Walkthrough. Euler's formula, the edge bound, and why K₅ is non-planar.
• Proof. See why V - E + F = 2 — build any planar graph from a spanning tree.
• Practice. Apply Euler's formula to find faces.
• Hardest. Show that K₃,₃ has no planar drawing.

Not sure where to start? Take the ten-question placement test.