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 seemingly simple property has deep mathematical consequences and practical applications in circuit design, geography, and more!
In this section, you'll discover Euler's famous formula, learn why some graphs can never be drawn without crossings, and explore the faces that planar embeddings create.
A planar graph can be drawn on a plane without any edges crossing. Drag the vertices to try to eliminate all crossings!
Euler's formula states that for any connected planar graph: V - E + F = 2. Click to add vertices, click two vertices to toggle edges, right-click to remove.
Click: add vertex or select • Click two vertices: toggle edge • Right-click: remove vertex
Kuratowski's theorem states that a graph is planar if and only if it doesn't contain K₅ or K₃,₃ as a subdivision. Try to draw these without crossings — it's impossible!
Drag vertices to try to eliminate crossings
A graph G is planar if and only if G does not contain a subdivision of K₅ or K₃,₃. A subdivision replaces edges with paths — so any graph with K₅ or K₃,₃ "hidden inside" (possibly with extra vertices on edges) is also non-planar.
A face is a region bounded by edges in a planar embedding. Every planar graph has an outer (unbounded) face. Click on colored regions to explore face properties!
Click on colored regions to select faces
1. Planar Graphs: A graph is planar if it can be embedded in the plane without edge crossings. Many graphs can be rearranged to be planar, but some fundamentally cannot—their structure guarantees crossings in any drawing.
2. Euler's Formula: 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). This elegant formula dates to 1752 and connects graph topology to geometry.
3. Kuratowski's Theorem: A graph is non-planar if and only if it contains K₅ (complete graph on 5 vertices) or K₃,₃ (complete bipartite graph) as a subdivision. These are the minimal non-planar graphs.
4. Faces: A planar embedding divides the plane into faces. The sum of all face degrees equals 2|E| (handshaking lemma for faces). Understanding faces is key to proving Euler's formula and the Four Color Theorem.
Next Up: In the next section, you'll learn about network flows — how to model and optimize flow through networks, including the famous max-flow min-cut theorem!