# Chapter 40. Kuratowski's Theorem

# Chapter 40. Kuratowski's Theorem

Kuratowski's theorem gives a complete forbidden-subgraph characterization of finite planar graphs. It says that the only essential obstructions to planarity are two graphs: \(K_5\) and \(K_{3,3}\), together with their subdivisions.

The theorem is deeper than Euler's formula. Euler's formula gives useful tests for nonplanarity, but those tests are only necessary conditions. Kuratowski's theorem gives an exact condition.

## 40.1 The Two Basic Obstructions

The complete graph \(K_5\) has five vertices, with every pair of distinct vertices joined by an edge. It has

$$
v = 5, \qquad e = 10.
$$

If \(K_5\) were planar, it would satisfy

$$
e \leq 3v - 6.
$$

But

$$
3v - 6 = 3 \cdot 5 - 6 = 9,
$$

and \(10 > 9\). Therefore \(K_5\) is nonplanar.

The complete bipartite graph \(K_{3,3}\) has two parts of size \(3\). Each vertex in one part is adjacent to all vertices in the other part. It has

$$
v = 6, \qquad e = 9.
$$

If \(K_{3,3}\) were planar, the bipartite planar bound would give

$$
e \leq 2v - 4.
$$

But

$$
2v - 4 = 2 \cdot 6 - 4 = 8,
$$

and \(9 > 8\). Therefore \(K_{3,3}\) is nonplanar.

These two graphs are the basic nonplanar patterns.

## 40.2 Subdivision

A subdivision of a graph is obtained by replacing edges with paths.

More precisely, to subdivide an edge \(uv\), insert a new vertex \(w\) on the edge and replace \(uv\) by two edges:

$$
uw,\qquad wv.
$$

Repeating this operation produces a subdivision of the original graph.

For example, an edge

$$
u - v
$$

may be replaced by a path

$$
u - x_1 - x_2 - \cdots - x_k - v.
$$

The new vertices \(x_1,\ldots,x_k\) are subdivision vertices. They have degree \(2\) within the subdivided edge-path.

Subdivision changes the number of vertices and edges, but it does not change the topological shape of the graph. A subdivided edge is still a curve connecting the same original endpoints.

## 40.3 Subdivision Preserves Planarity

Subdivision does not change planarity. A graph is planar exactly when any subdivision of it is planar. If a graph is drawn without crossings, inserting a new vertex along an edge keeps the drawing planar. Conversely, if a subdivision is drawn without crossings, each subdivided path can be treated as a single curve joining its original endpoints. Thus the original graph is planar.

This observation explains why Kuratowski's theorem uses subdivisions rather than only \(K_5\) and \(K_{3,3}\) themselves. A graph may not literally contain \(K_5\) or \(K_{3,3}\) as a subgraph, but it may contain one of them with some edges stretched into paths.

## 40.4 Statement of Kuratowski's Theorem

Let \(G\) be a finite graph. Then \(G\) is planar if and only if \(G\) contains no subgraph that is a subdivision of \(K_5\) or \(K_{3,3}\). Such a subgraph is often called a Kuratowski subgraph.

Equivalently:

$$
G \text{ is planar}
$$

if and only if

$$
G \text{ contains no subdivision of } K_5 \text{ and no subdivision of } K_{3,3}.
$$

This is a complete characterization. It gives both directions:

| Direction | Meaning |
|---|---|
| If \(G\) contains such a subdivision, then \(G\) is nonplanar | Nonplanarity is inherited from \(K_5\) or \(K_{3,3}\) |
| If \(G\) is nonplanar, then \(G\) contains such a subdivision | Every finite obstruction contains one of the two basic patterns |

The first direction is relatively direct. The second direction is the difficult part of the theorem.

## 40.5 Why Containing a Kuratowski Subgraph Forces Nonplanarity

Suppose \(G\) contains a subgraph \(H\) that is a subdivision of \(K_5\) or \(K_{3,3}\).

If \(G\) were planar, then every subgraph of \(G\) would also be planar. Thus \(H\) would be planar.

But subdivision preserves planarity. Therefore the original graph, either \(K_5\) or \(K_{3,3}\), would be planar.

This is impossible. Both \(K_5\) and \(K_{3,3}\) are nonplanar.

Therefore \(G\) cannot be planar.

The reasoning has the following form:

$$
G \text{ planar}
\Rightarrow
H \text{ planar}
\Rightarrow
K_5 \text{ or } K_{3,3} \text{ planar},
$$

which contradicts the known nonplanarity of \(K_5\) and \(K_{3,3}\).

## 40.6 Why the Converse Is Deep

The converse says that every finite nonplanar graph contains one of these two obstructions after subdivision.

This is not obvious. A nonplanar graph may be large, sparse, irregular, and far removed in appearance from either \(K_5\) or \(K_{3,3}\). Kuratowski's theorem says that inside every such graph there is still a hidden copy of one of these two topological patterns.

The proof usually proceeds by considering a minimal nonplanar graph and showing that it must contain a subdivision of \(K_5\) or \(K_{3,3}\). Modern proofs often use connectivity, cycles, bridges, and embeddings of subgraphs. The complete proof is longer than the elementary proofs of Euler's formula and the planar edge bounds.

## 40.7 Homeomorphic Graphs

Two graphs are often called homeomorphic if they can be obtained from a common graph by subdivision. In this language, Kuratowski's theorem says:

A finite graph is planar if and only if it contains no subgraph homeomorphic to \(K_5\) or \(K_{3,3}\).

The word homeomorphic here reflects the topological nature of planarity. Edges are treated as curves. Subdividing an edge only inserts extra degree-two vertices along that curve. It does not alter the essential shape.

## 40.8 Examples

Consider a graph \(G\) that contains five distinguished vertices

$$
a,b,c,d,e
$$

such that every pair is connected by an internally vertex-disjoint path, and these paths together form a subdivision of \(K_5\). Then \(G\) is nonplanar.

The five distinguished vertices play the role of the vertices of \(K_5\). The paths between them play the role of the edges of \(K_5\).

Similarly, suppose \(G\) contains six distinguished vertices split into two sets

$$
\{a_1,a_2,a_3\}
$$

and

$$
\{b_1,b_2,b_3\},
$$

with internally vertex-disjoint paths joining each \(a_i\) to each \(b_j\). Then \(G\) contains a subdivision of \(K_{3,3}\), so \(G\) is nonplanar.

## 40.9 Kuratowski Subgraphs

A Kuratowski subgraph is a subgraph that is a subdivision of \(K_5\) or \(K_{3,3}\). Finding such a subgraph gives a certificate of nonplanarity.

This is useful because the certificate is local. To prove that a large graph is nonplanar, it is enough to exhibit one Kuratowski subgraph inside it. There is no need to analyze every possible drawing of the full graph.

For example, if a network has thousands of vertices but contains a subdivision of \(K_{3,3}\), then the entire network is nonplanar.

## 40.10 Relation to Wagner's Theorem

Kuratowski's theorem characterizes planar graphs by forbidden subdivisions. Wagner's theorem gives a related characterization by forbidden minors.

A graph minor is obtained by deleting vertices, deleting edges, and contracting edges. Wagner's theorem states that a finite graph is planar if and only if it has no \(K_5\) minor and no \(K_{3,3}\) minor. Kuratowski's theorem and Wagner's theorem are closely related, but they use different containment notions: subdivision for Kuratowski, minor for Wagner.

| Theorem | Forbidden objects | Containment notion |
|---|---|---|
| Kuratowski | \(K_5\), \(K_{3,3}\) | Subdivision subgraph |
| Wagner | \(K_5\), \(K_{3,3}\) | Minor |

Both theorems express the same central fact: planar graphs are exactly the graphs that avoid the two fundamental nonplanar patterns.

## 40.11 Planarity Testing

Kuratowski's theorem is structural, but it also has algorithmic meaning. If a graph is nonplanar, a planarity-testing algorithm can return a Kuratowski subgraph as a certificate. Such a certificate can be checked directly: verify that the indicated subgraph is a subdivision of \(K_5\) or \(K_{3,3}\). Linear-time algorithms are known for finding Kuratowski subgraphs in nonplanar graphs.

This separates two tasks:

| Task | Certificate |
|---|---|
| Prove planarity | Provide a planar embedding |
| Prove nonplanarity | Provide a Kuratowski subgraph |

A good planarity algorithm can therefore give evidence in either case.

## 40.12 Summary

Kuratowski's theorem gives the fundamental forbidden-subgraph characterization of finite planar graphs:

$$
G \text{ is planar}
\quad\Longleftrightarrow\quad
G \text{ contains no subdivision of } K_5 \text{ or } K_{3,3}.
$$

The theorem rests on three central ideas. First, \(K_5\) and \(K_{3,3}\) are nonplanar. Second, subdivision preserves planarity. Third, every finite nonplanar graph contains one of these two graphs in subdivided form.

Euler's formula gives useful counting obstructions. Kuratowski's theorem gives a complete structural obstruction. It identifies the exact topological patterns that prevent a graph from being drawn in the plane without crossings.