Planar Graphs Summary

Graph Theory · Axiom Academy

Let's review the key concepts of planar graphs, embeddings, and fundamental theorems. Definition: A graph is planar if it can be drawn in the plane with no edge crossings Embedding: A specific drawing of a planar graph with no crossings in the plane Faces: Regions bounded by edges in a planar embedding, including the unbounded outer face Why It Matters: Models circuit board design, geographical maps, and network layouts where crossings are costly or impossible K₅: The complete graph on 5 vertices is not planar—too many edges for vertices K₃,₃: The complete bipartite graph with partitions of size 3 is not planar—utility graph problem Subdivisions: Graphs obtained by adding vertices along edges preserve planarity properties Key Insight: These two graphs are the fundamental obstructions to planarity Example: Proving K₅ is Non-Planar Step 1 - Count: K₅ has v = 5 vertices and e = 10 edges (complete graph has e = v(v-1)/2) Step 2 - Assume Planar: If K₅ were planar, Euler's formula gives f = 2 - v + e = 2 - 5 + 10 = 7 faces Step 3 - Edge-Face Inequality: Each face needs at least 3 edges, each edge borders at most 2 faces, so 2e ≥ 3f, giving 20 ≥ 21 Step 4 - Contradiction: This is impossible, so K₅ cannot be planar. The assumption was false. Statement: A graph is planar if and only if it contains no subdivision of K₅ or K₃,₃ Subdivision: Adding vertices of degree 2 along edges doesn't change planarity—it just "stretches" edges

This is the written version of the interactive lesson above. See the full Graph Theory course.