Course contentsShow
← Mathematics
Lesson 2694 of 3,12153. Graph TheoryFree lesson

Kuratowski's Theorem and Graph Subdivisions

State Kuratowski's theorem: a graph is planar if and only if it contains no subdivision of K₅ or K₃,₃.

Kuratowski's Theorem and Graph Subdivisions

What you'll learn: You'll discover a powerful theorem that precisely characterizes which graphs can be drawn on a plane without edge crossings.

The Core Idea

After learning that K₅ and K₃,₃ are the smallest non-planar graphs, you might wonder: are these the only obstructions to planarity? Kuratowski's Theorem answers with a resounding insight.

First, understand graph subdivision: you subdivide a graph by inserting new vertices along existing edges. For example, replacing edge (u,v) with a path u→w→v subdivides that edge. Think of it like adding waypoints on a road—the route is still there, just with extra stops.

Kuratowski's Theorem

The theorem states: A graph is planar if and only if it contains no subdivision of K₅ or K₃,₃ as a subgraph.

In plain English: a graph can be drawn without crossings precisely when you can't find a "stretched-out" copy of K₅ or K₃,₃ hiding within it.

Why This Matters

This theorem gives us a complete characterization of planarity. It's not just that K₅ and K₃,₃ themselves are problematic—any graph that contains their "essence" (via subdivision) is also non-planar. The subdivisions preserve the fundamental topological structure that causes crossings.

Analogy: Think of K₅ and K₃,₃ as genetic markers for non-planarity. Even if you insert extra vertices (like adding segments to DNA), the fundamental "non-planar gene" remains, and the graph still can't be drawn flat.

Practical Use

To prove a graph is non-planar using Kuratowski's Theorem, find a subgraph that's a subdivision of K₅ or K₃,₃. Conversely, if you can show no such subdivision exists, the graph must be planar.

Key Takeaway: Kuratowski's Theorem elegantly reduces the planarity question to detecting subdivisions of exactly two forbidden structures: K₅ and K₃,₃.