Euler's formula, planarity testing, and Kuratowski's theorem
Can you draw a graph so that no two edges cross? Most small graphs untangle with a little dragging, but two famous ones never will.
Pick a graph and drag its vertices to remove every crossing. K4 and the cube untangle; K5 and K3,3 never do.
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.
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. 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.
Click empty space to add a vertex, click two vertices to toggle an edge, and right-click to remove a vertex. Watch V - E + F stay at 2 while the graph stays connected.
Click: add vertex or select • Click two vertices: toggle edge • Right-click: remove vertex
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). 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.
Switch between K5 and K3,3 and drag their vertices to try for a crossing-free drawing. At least one crossing always remains.
Drag vertices to try to eliminate crossings
A graph is planar if and only if it contains no subdivision of K5 or K3,3. 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.
Click the colored regions to see each face's boundary vertices and degree. Check that the face degrees add up to 2|E|.
Click on colored regions to select faces
A planar embedding divides the plane into regions called faces, including one unbounded outer face. 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.
Spot a mistake or have an idea?