Proof of Kuratowski's Theorem

The Planarity Characterization

Kuratowski’s theorem identifies exactly which finite simple graphs fail to be planar: those containing a subdivision of one of two specific graphs. A subdivision replaces edges by paths, with the replacement paths internally disjoint. Thus the obstruction need not appear as a literal copy of either graph; its vertices and edges may be spread across longer paths.

All graphs below are finite and simple. The graphs \(K_5\) and \(K_{3,3}\) are the complete graph on five vertices and the complete bipartite graph with parts of size three, respectively. A graph contains a subdivision of either one when it has a subgraph that is such a subdivision; extra vertices and edges elsewhere in the graph do not affect containment.

The proof has two distinct parts. First, neither forbidden graph, nor any subdivision of it, is planar. Second, if a graph is nonplanar, a minimal nonplanar subgraph contains one of these subdivisions. The second part is the substantive structural step: minimality by itself does not identify the obstruction.

Why the Two Graphs and Their Subdivisions Obstruct Planarity

We use two elementary facts about plane embeddings. Deleting vertices or edges from a plane embedding leaves a plane embedding of the remaining graph. Also, subdividing an edge preserves planarity: place the new vertex on the arc representing that edge and divide the arc into two arcs. Repeating this operation handles any finite number of subdivisions. Consequently, if a graph containing a subdivision of \(K_5\) or \(K_{3,3}\) were planar, deleting the other parts of the graph would give a plane embedding of the subdivision, and suppressing its degree-two vertices would give a plane embedding of the corresponding \(K_5\) or \(K_{3,3}\). We now verify that neither is planar.

These arguments use face-boundary lengths only under hypotheses that justify the lower bounds. In particular, a bridge can occur twice in a facial boundary walk, producing length two. It would be incorrect to claim that every face in every simple planar graph with at least three vertices has boundary length at least three.

The Minimal-Subgraph Reduction

For the converse direction, we use the Kuratowski Reduction Lemma, established in the earlier material on the Kuratowski reduction. We state the precise form needed here. Its bridge-attachment analysis is the nontrivial structural ingredient; it is not a consequence of minimality alone.

The lemma uses bridges relative to a subgraph: these include edges outside the subgraph whose endpoints lie in it, and components outside it together with their incident edges to it. The vertices where a bridge meets the subgraph are its attachments. The reduction analyzes how such bridges can be attached to a planar subgraph and uses minimal nonplanarity to restrict the possible attachment patterns. The lemma’s conclusion is exactly the structural fact required below. We invoke it as an independently established result rather than treating it as something that follows automatically from choosing a minimal counterexample.

Proof. Among the nonplanar subgraphs of \(G\), choose one, \(H\), with the fewest vertices and edges in total. Such a choice exists because \(G\) is finite and \(G\) itself is a nonplanar subgraph. Every proper subgraph of \(H\) has fewer vertices and edges in total than \(H\); by the choice of \(H\), it cannot be nonplanar. Thus \(H\) is nonplanar and all its proper subgraphs are planar. The Kuratowski Reduction Lemma applies and gives a subdivision of \(K_5\) or \(K_{3,3}\) in \(H\). Since \(H\) is a subgraph of \(G\), the same subdivision occurs in \(G\). \(\square\)

This use of minimality requires no assumption that \(G\) is connected. If \(G\) is disconnected but nonplanar, the selected nonplanar subgraph still exists, and the reduction lemma applies to it. Isolated vertices or other components cannot invalidate the argument: they are simply not required to be part of the chosen subgraph.

Proof of Kuratowski’s Theorem

Proof. First suppose that \(G\) contains a subdivision of \(K_5\) or \(K_{3,3}\). If \(G\) were planar, deleting all vertices and edges outside that subdivision would leave a plane embedding of the subdivision. Suppressing its degree-two vertices would then give a plane embedding of \(K_5\) or \(K_{3,3}\). The Euler calculations above show that both are nonplanar, so \(G\) cannot be planar.

Conversely, suppose \(G\) is nonplanar. The proposition, proved using the Kuratowski Reduction Lemma, shows that \(G\) contains a subdivision of \(K_5\) or \(K_{3,3}\). Therefore, if \(G\) contains neither subdivision, it must be planar. These two implications establish the equivalence. \(\square\)

Common Pitfalls and Why the Reduction Matters

Mistake: applying a face-length bound without checking bridges. Consider the simple planar graph with \(V=\{a,b,c\}\) and \(E=\{ab\}\). It has an isolated vertex \(c\), and its one face has boundary walk \(a,b,a\), of length two. Thus it is false that every face boundary in every simple planar graph with at least three vertices has length at least three. This example does not contradict the calculations for \(K_5\) or \(K_{3,3}\): those connected graphs have no bridges, and their facial boundary walks have the stronger length bounds used above.

Mistake: assuming minimality alone produces a forbidden subdivision. Minimality tells us that every proper subgraph of the selected nonplanar graph is planar. It does not, without further structural reasoning, specify the shape of that graph. The Kuratowski Reduction Lemma supplies that missing reasoning through its bridge-attachment analysis. Keeping this distinction explicit makes the proof’s dependency clear.

The theorem is useful because it converts an existence question about drawings into a structural criterion. To prove a particular graph nonplanar, it is enough to identify one of the two subdivisions. To prove planarity through the characterization, one must rule out both types of subdivision; simply failing to spot one is not a proof of absence.