Euler's formula, planarity testing, and Kuratowski's theorem
A planar graph is one that can be drawn in the plane without any edges crossing. This property has deep consequences: Euler's formula relates vertices, edges, and faces in any planar embedding, and Kuratowski's theorem characterizes exactly which graphs are non-planar.
Planarity matters in circuit board layout, geographic information systems, and the proof of the Four Color Theorem. Understanding the structure of planar embeddings -- especially faces and their relationship to edges -- provides powerful tools for reasoning about graphs.
Drag vertices to try to draw the graph without any edge crossings. Planar graphs like K4 can always be rearranged to eliminate crossings, while non-planar graphs like K5 and K3,3 will always have at least one crossing.
Key insight: Planarity is a topological property of the graph, not a property of any particular drawing. A graph is planar if there exists some arrangement of its vertices that avoids all crossings.
For any connected planar graph, V - E + F = 2, where V is vertices, E is edges, and F is faces (including the outer unbounded face). Click to add vertices, click two vertices to toggle edges, and right-click to remove vertices. Watch the formula hold as you modify the graph.
Click: add vertex or select • Click two vertices: toggle edge • Right-click: remove vertex
Key insight: Euler's formula, discovered in 1752, is one of the most elegant results in combinatorics. It can be used to prove that K5 and K3,3 are non-planar, and it generalizes to higher-dimensional polytopes.
A graph is planar if and only if it contains no subdivision of K5 or K3,3. Switch between these two forbidden minors and try to drag their vertices into a crossing-free arrangement -- you will find it impossible.
Drag vertices to try to eliminate crossings
Key insight: Kuratowski's theorem (1930) gives a complete characterization: K5 and K3,3 are the only two "forbidden subgraphs" for planarity. Any non-planar graph contains one of them as a subdivision.
A planar embedding divides the plane into regions called faces, including one unbounded outer face. Click on the colored regions to inspect face properties such as boundary vertices and face degree. Verify the handshaking lemma for faces: the sum of all face degrees equals 2|E|.
Click on colored regions to select faces
Key insight: Every planar graph has exactly one unbounded outer face. The face handshaking lemma -- the sum of face degrees equals 2|E| -- mirrors the vertex handshaking lemma and is key to many proofs involving planar graphs.