From Kuratowski Subdivisions to Forbidden Minors

From Paths to Edges

A subdivision replaces edges by paths: each original edge is stretched across a sequence of edges, but the original vertices remain as the endpoints. When the graph being subdivided is \(K_5\) or \(K_{3,3}\), the resulting paths can be shortened again by contraction. The key is to contract the internal vertices of each path into one endpoint, while keeping the two original endpoints distinct. This tutorial makes that process precise and tracks it in explicit graphs.

All graphs below are finite and simple. A subgraph is obtained by deleting vertices and edges. An edge contraction identifies the two endpoints of an edge; loops created by contraction are deleted, and repeated edges are treated as a single edge. A graph \(H\) is a minor of \(G\) if it can be obtained from \(G\) by a sequence of vertex deletions, edge deletions and edge contractions. A subdivision of a graph \(H\) replaces each edge \(uv\) of \(H\) with a \(u\)-\(v\) path. The internal vertices of these paths are distinct from the vertices of \(H\), and paths replacing different edges have disjoint internal vertices.

A branch set represents all the vertices of \(G\) that will be merged to form one vertex of \(H\). The condition about edges between branch sets ensures that each required edge of \(H\) survives. Extra edges do not cause difficulty: they can be deleted if they are not wanted.

The Branch-Set Test for a Minor

Proof. First suppose \(H\) is obtained from \(G\) by deletions and contractions. Consider only the vertices of \(G\) that remain after any initial vertex deletions. At each stage, associate to every current vertex the set of original vertices that have been merged into it. Initially each such set is a singleton. When an edge is contracted, the two associated sets are united. They are disjoint before the union, and an edge between the two current vertices shows that their union induces a connected subgraph of the original graph. Thus the associated sets remain nonempty, pairwise disjoint and connected. Edge deletions do not change them. When the process ends, each vertex \(x\) of \(H\) has a nonempty connected set \(B_x\) of original vertices. Each edge \(xy\) of \(H\) comes from an edge of \(G\) whose endpoints lie in \(B_x\) and \(B_y\), so these sets are branch sets.

Conversely, suppose \(G\) has branch sets \(B_x\) for \(x\in V(H)\). Delete all vertices not in their union. Within each \(B_x\), choose a spanning tree of the connected graph \(G[B_x]\), and contract the tree's edges. This merges exactly the vertices of \(B_x\) into one vertex: contracting a tree with \(r\) vertices takes \(r-1\) edge contractions, and cannot merge that set with another branch set. After doing this for every \(x\), the resulting graph has one vertex for each vertex of \(H\). For every edge \(xy\) of \(H\), an edge between \(B_x\) and \(B_y\) gives the edge \(xy\) after contraction. Delete any edges that do not belong to \(H\). The result is \(H\), including when \(H\) has isolated vertices, since their nonempty branch sets still contract to vertices. If \(H\) has no vertices, delete every vertex of \(G\). Thus \(H\) is a minor of \(G\). \(\square\)

The theorem explains the contraction procedure for a subdivision. Give each original vertex \(x\) the branch set consisting of \(x\) together with the internal vertices on paths assigned to \(x\). For each replaced edge \(xy\), assign all its internal vertices to one endpoint, say \(x\), and none to \(y\). These sets are disjoint because the replacement paths have disjoint interiors. Each set is connected through its original vertex, and the last edge of the \(x\)-to-\(y\) path joins the two endpoint sets. Therefore they are branch sets for the original graph.

Contracting a Subdivision of \(K_5\)

There is a useful sequence-level view of the same operation. On a replacement path \(u,w_1,\ldots,w_k,v\), contract \(uw_1\), then the edge from the merged vertex to \(w_2\), continuing until all internal vertices have merged into \(u\). The last edge still joins the merged set to \(v\). In the example, the path \(1,6,2\) requires only the contraction of \(16\); its edge \(62\) remains to represent \(12\).

Contracting a Subdivision of \(K_{3,3}\)

The bipartition is not needed to perform the contractions, but it is a useful check in this example: every edge of \(K_{3,3}\) must join the two classes. The construction does not require all replacement paths to have the same length. Each path can be contracted separately because its internal vertices belong to no other replacement path.

When the Subdivision Sits Inside a Larger Graph

This illustrates a practical order of operations: identify the subdivision, discard irrelevant vertices and edges, then contract the replacement paths. The branch-set test gives another route: specify the sets first, verify they are disjoint and connected, and check every required adjacency. Both approaches describe the same minor construction.

A Common Contraction Error

Pitfall: contracting every edge of a replacement path can merge its two original endpoints. For the path \(1,6,2\), contracting \(16\) and then the resulting edge from the merged vertex to \(2\) identifies \(1\) and \(2\). The path no longer supplies an edge between two distinct vertices, so it does not represent the edge \(12\) of \(K_5\).

The correction is to merge the internal vertices into just one endpoint and stop before merging the other endpoint. Contracting \(16\) makes \(\{1,6\}\) one branch set, while \(62\) remains an edge from that set to the separate set \(\{2\}\). In general, for a replacement path with distinct endpoints \(u,v\), assign its internal vertices to \(u\), contract them into \(u\), and preserve the final connection to \(v\).

The distinction between a subdivision and a minor is important here. A subdivision preserves the original vertices and lengthens edges into paths. A minor may also be obtained by deletions, and its edge contractions identify vertices. The branch-set theorem records precisely which vertices are to be identified and why the required adjacencies survive.