From Kuratowski Subdivisions to Minors
Kuratowski’s theorem describes nonplanarity using subdivisions: a finite graph is nonplanar exactly when it contains a subdivision of \(K_5\) or \(K_{3,3}\). Wagner’s theorem gives an equivalent description using minors. The key link is that a subdivided edge can be restored to a single edge by contraction. In the other direction, deleting or contracting edges cannot turn a planar graph into a nonplanar one.
Throughout, graphs are finite and simple unless stated otherwise. A graph is planar if it can be drawn in the plane with edges meeting only at common endpoints. A particular such drawing is a plane embedding. A subdivision of a graph replaces each edge by a path with the same endpoints; the internal vertices of these paths are new and are disjoint from one another.
These operations play different roles. Deleting a vertex removes it and all its incident edges; deleting an edge removes only that edge. Contracting an edge identifies its endpoints, which can join parts of a graph that were previously separated by a path. In particular, deleting the internal vertex of a subdivided edge does not restore that edge.
Why Planarity Survives Minor Operations
Proof. Let \(G\) be planar and fix a plane embedding. Deleting an edge means erasing its arc, and deleting a vertex means erasing that vertex and its incident arcs; neither operation creates a crossing. For contraction, consider an embedded edge \(uv\). Choose a small neighborhood of the arc \(uv\) and its endpoints that contains no other vertices and meets other edge-arcs only where they enter \(u\) or \(v\). Replace this neighborhood by one vertex, and connect the entering arcs to that vertex in the order in which they meet the neighborhood’s boundary. Those arcs can be drawn without crossing inside the neighborhood. Outside it, leave the embedding unchanged. This gives an embedding of the contracted graph; removing any loops and merging any parallel edges preserves planarity as well. Each permitted operation therefore preserves planarity, and applying this argument successively proves the claim for any finite sequence of operations. \(\square\)
We will use that \(K_5\) and \(K_{3,3}\) are nonplanar. Here is a check from the standard planar edge bounds, which follow from Euler’s formula. A connected simple planar graph with \(n\ge3\) vertices has at most \(3n-6\) edges: each face has boundary length at least \(3\), so \(3f\le2m\), while Euler’s formula gives \(n-m+f=2\). Combining them gives \(m\le3n-6\). A connected, bridgeless, simple bipartite planar graph has at most \(2n-4\) edges: each face boundary has length at least \(4\), so \(4f\le2m\), and Euler’s formula gives \(m\le2n-4\). The boundary-length conditions apply here because the graphs are simple, and a boundary of length \(2\) would require a bridge; bipartiteness rules out odd boundary lengths.
The graph \(K_5\) is connected, simple and bridgeless, with \(n=5\) and \(m=10\). The first bound would require \(10\le3(5)-6=9\), which is false. The graph \(K_{3,3}\) is connected, simple, bridgeless and bipartite, with \(n=6\) and \(m=3\cdot3=9\). The bipartite bound would require \(9\le2(6)-4=8\), also false. Thus neither graph is planar.
Worked Example: Contracting a Subdivision of \(K_5\)
Let \(G\) have vertices \(\{a_1,a_2,a_3,a_4,a_5\}\cup\{x_{ij}:1\le i<j\le5\}\), and edges \(a_ix_{ij}\) and \(x_{ij}a_j\) for every pair \(1\le i<j\le5\). This is the graph formed by subdividing every edge of \(K_5\) once. There are \(\binom{5}{2}=10\) pairs, hence \(5+10=15\) vertices and \(2\cdot10=20\) edges.
For each pair \(ij\), contract \(x_{ij}a_j\). The other edge on that subdivided path becomes \(a_ia_j\). The table tracks the number \(k\) of paths processed; each contraction removes one internal vertex and replaces two path edges by one edge, so the vertex and edge counts each decrease by one.
| Paths processed, in order | \(k\) | Vertices \(15-k\) | Edges \(20-k\) |
|---|---|---|---|
| None | 0 | 15 | 20 |
| \(12\) | 1 | 14 | 19 |
| \(12,13\) | 2 | 13 | 18 |
| \(12,13,14\) | 3 | 12 | 17 |
| \(12,13,14,15\) | 4 | 11 | 16 |
| \(12,13,14,15,23\) | 5 | 10 | 15 |
| \(12,13,14,15,23,24\) | 6 | 9 | 14 |
| \(12,13,14,15,23,24,25\) | 7 | 8 | 13 |
| \(12,13,14,15,23,24,25,34\) | 8 | 7 | 12 |
| \(12,13,14,15,23,24,25,34,35\) | 9 | 6 | 11 |
| \(12,13,14,15,23,24,25,34,35,45\) | 10 | 5 | 10 |
Check: after all ten contractions, the remaining vertices are \(a_1,\dots,a_5\), and for every pair \(i<j\) the edge \(a_ia_j\) is present. There are \(\binom{5}{2}=10\) such edges, agreeing with the final count. The result is \(K_5\).
Wagner’s Planar Minor Criterion
Proof. First suppose \(G\) is planar. By the lemma, every minor of \(G\) is planar. Since \(K_5\) and \(K_{3,3}\) are nonplanar, neither can be a minor of \(G\).
Conversely, suppose \(G\) has neither \(K_5\) nor \(K_{3,3}\) as a minor. We prove that \(G\) is planar by contradiction. If \(G\) were nonplanar, Kuratowski’s theorem would give a subgraph \(H\) of \(G\) that is a subdivision of \(K_5\) or \(K_{3,3}\). Delete vertices and edges outside \(H\), leaving that subdivision. For each path replacing an edge of the underlying \(K_5\) or \(K_{3,3}\), contract its internal edges until it becomes a single edge. The internal vertices of the subdivision paths are disjoint, so these contractions recover the underlying graph without identifying distinct branch vertices. Thus \(G\) has \(K_5\) or \(K_{3,3}\) as a minor, contrary to the assumption. Therefore \(G\) is planar. \(\square\)
The first direction uses preservation of planarity under minor operations. The second uses Kuratowski’s theorem and the fact that contracting each subdivided path recovers the original graph. Both directions matter: a subdivision is a particular subgraph structure, whereas a minor may also use deletions and contractions in other parts of the graph.
Worked Example: Recovering a \(K_{3,3}\) Minor
Let \(G\) have vertices \(\{L_1,L_2,L_3,R_1,R_2,R_3,x,y\}\). Include all nine \(L_iR_j\) edges except \(L_1R_1\) and \(L_2R_3\); replace those two edges by \(L_1x,xR_1\) and \(L_2y,yR_3\). Thus the seven direct edges are \(L_1R_2,L_1R_3,L_2R_1,L_2R_2,L_3R_1,L_3R_2,L_3R_3\), and the four other edges are the two length-two paths just specified. The graph has \(6+2=8\) vertices and \(7+4=11\) edges.
Contract \(xR_1\). The edge \(L_1x\) becomes \(L_1R_1\), leaving \(7+1+2=10\) edges and \(7\) vertices. Then contract \(yR_3\). The edge \(L_2y\) becomes \(L_2R_3\), leaving \(10-1=9\) edges and \(7-1=6\) vertices. All nine pairs \(L_iR_j\) are now adjacent, and there are no edges within either side. The resulting graph is \(K_{3,3}\).
Check: the nine edges are exactly the \(3\cdot3=9\) possible pairs between \(\{L_1,L_2,L_3\}\) and \(\{R_1,R_2,R_3\}\). No vertices were identified with one another within either side, so the result has the required six vertices and is \(K_{3,3}\).
Worked Example: A Planar Graph with Neither Forbidden Minor
Let \(G=K_4\), with vertex set \(\{1,2,3,4\}\) and edge set \(\{12,13,14,23,24,34\}\). It is planar: draw the triangle \(123\), place vertex \(4\) inside it, and join \(4\) to each of \(1,2,3\) inside the triangle. The six listed edges are present, and the three edges from \(4\) meet only at \(4\).
Every minor operation leaves the number of vertices unchanged or decreases it. Since \(G\) has four vertices, none of its minors can have the five vertices of \(K_5\) or the six vertices of \(K_{3,3}\). Hence neither forbidden graph is a minor of \(G\).
Check: the displayed edge set has \(\binom{4}{2}=4\cdot3/2=6\) edges, as required for \(K_4\). Its planar drawing and its order of four verify, respectively, planarity and the impossibility of either forbidden minor.
Common Pitfall: Deletion Is Not Contraction
Suppose a subdivided edge is the path \(a-x-b\). A mistaken argument says that deleting \(x\) leaves the edge \(ab\). It does not: deleting \(x\) removes both \(ax\) and \(xb\), leaving no connection between \(a\) and \(b\) from this path. The correct operation is to contract \(xb\); then \(ax\) becomes \(ab\). This distinction is precisely why subdivisions yield the forbidden minors by contraction, not by simply deleting their internal vertices.
Wagner’s criterion is useful because a minor obstruction can be hidden behind subdivisions or extra graph structure. The theorem says that, for planarity, it is enough to know whether the two specific graphs occur after deletions and contractions. Kuratowski’s theorem supplies the obstruction as a subdivision; contracting paths translates that certificate into the minor language.
Check Your Understanding
For each question, justify your answer using the definitions or the proof of Wagner’s theorem.
- State the three operations allowed when forming a graph minor, and explain how simple-graph conventions are maintained after contraction.
- Why does planarity of \(G\) rule out every nonplanar minor of \(G\)?
- Given a subdivision of \(K_5\), describe how its subdivided paths can be contracted to recover \(K_5\).
- In the path \(a-x-b\), what graph results from deleting \(x\), and what graph results from contracting \(xb\)?
- Why does the absence of \(K_5\) and \(K_{3,3}\) minors imply planarity when Kuratowski’s theorem is available?