Planarity & Euler's Formula

A graph is planar if it can be drawn in the plane without edge crossings. Euler's formula $v - e + f = 2$ relates vertices, edges, and faces. We derive edge bounds and learn Kuratowski's theorem: a graph is planar iff it has no subdivision of $K_5$ or $K_{3,3}$ .

Learning Objectives

State and prove Euler's formula for connected planar graphs

Derive edge bounds: e ≤ 3v - 6 and e ≤ 2v - 4 (triangle-free)

Apply Kuratowski's theorem to prove non-planarity

Understand and use the Five Color Theorem

Key Concepts

Planar Graphs & Euler's Formula

A graph is planar if it can be embedded in the plane with no edge crossings. Such a drawing divides the plane into faces (regions), including one unbounded outer face.

Euler's formula is the fundamental equation of planar graphs.

-
Every face is bounded by at least 3 edges (in a simple graph), giving $2e \geq 3f$
-
Combining with Euler's formula: $e \leq 3v - 6$
-
Triangle-free: each face has $\geq 4$ boundary edges, giving $e \leq 2v - 4$
-
$K_5$ is not planar: $e = 10 > 3(5) - 6 = 9$
-
$K_{3,3}$ is not planar: $e = 9 > 2(6) - 4 = 8$ (it's triangle-free)

Kuratowski's Theorem

Kuratowski's theorem gives a complete characterization of planarity:

A graph is planar if and only if it contains no subdivision of $K_5$ or $K_{3,3}$ .

A subdivision of a graph $H$ is obtained by replacing edges with paths.

-
To prove non-planarity: find a subdivision of $K_5$ or $K_{3,3}$
-
Alternatively: use the edge bound ( $e > 3v - 6$ )
-
The Petersen graph is not planar (contains a $K_{3,3}$ subdivision)

Coloring Planar Graphs

Every planar graph is 5-colorable (Five Color Theorem). The famous Four Color Theorem states every planar graph is 4-colorable, but its proof requires computer assistance.

Every planar graph has a vertex of degree $\leq 5$ (since $e \leq 3v - 6$ implies average degree $< 6$ ).

-
Planar graphs have $\chi(G) \leq 5$ (provable) and $\chi(G) \leq 4$ (Four Color Theorem)
-
Every planar graph has a vertex with degree $\leq 5$
-
Proof of Five Color Theorem uses induction + Kempe chains

W5: Bipartite Graphs & Coloring W7: Covers, Independent Sets & Kruskal