Planar Graphs

Math for CS · Axiom Academy

Euler's formula, Kuratowski's theorem, and the four color theorem Planarity matters for circuit board design (can you route all wires on a single layer?), map coloring, and understanding the geometric structure of graphs. K_4 (complete graph on 4 vertices) is planar — draw it as a triangle with a vertex inside. K_5 and K_ 3,3 are not planar — proven by Kuratowski. The cornerstone of planar graph theory, discovered by Euler in 1758. where V = number of vertices, E = number of edges, and F = number of faces (regions), including the unbounded outer face. Edge Bounds from Euler's Formula Euler's formula places tight limits on how many edges a planar graph can have. Proof sketch: Every face is bounded by at least 3 edges, and every edge borders at most 2 faces. So , giving . Substituting into Euler's formula: , which simplifies to . Stronger Bound for Triangle-Free Graphs The edge-bound arguments above prove that K_5 and K_ 3,3 are not planar. Remarkably, these are the only fundamental obstructions. A subdivision of a graph H is obtained by replacing edges of H with paths (inserting vertices of degree 2 along edges). So a graph is non-planar precisely when you can find K_5 or K_ 3,3 "hidden" inside it, possibly with extra vertices along edges. How many colors do you need to color a planar graph so that no two adjacent vertices share a color? From , every planar graph has a vertex of degree . A simple induction proves 6 colors suffice. Five Color Theorem (Heawood, 1890)

This is the written version of the interactive lesson above. See the full Math for CS course.