Two Different Ways to Contain a Graph
Deleting edges and vertices, and contracting edges, can reveal a graph as a minor. A subdivision, by contrast, must already appear as a subgraph: its edges may be stretched into paths, but those paths must fit together without sharing internal vertices. Every subdivision can be contracted back to the graph it represents. The reverse implication fails, because contractions can combine several vertices into one even when no corresponding subdivision is present in the original graph.
All graphs in this tutorial are finite and simple. A subgraph of \(G\) is obtained by taking some vertices and some edges of \(G\) between those vertices. It need not include every edge of \(G\) whose endpoints it retains; that stronger requirement defines an induced subgraph. A contraction of an edge \(uv\) identifies \(u\) and \(v\) as one vertex and adjusts the incident edges accordingly. Loops are discarded and repeated edges are treated as a single edge, so the resulting graph is simple.
The internal vertices of a path are all its vertices except its two endpoints. Thus, the paths representing different edges may meet at a common endpoint that represents a vertex of \(H\), but they cannot share an internal vertex. A path of length one is allowed: that edge has no internal vertices and has not been subdivided.
A useful description of a minor is a minor model. It assigns to each vertex \(v\) of \(H\) a nonempty, connected set \(B_v\) of vertices of \(G\). These sets must be pairwise disjoint, and for each edge \(uv\) of \(H\), there must be at least one edge of \(G\) with one endpoint in \(B_u\) and the other in \(B_v\). Vertices and edges of \(G\) not used by the model can be deleted. Contracting each connected set to one vertex then produces \(H\), after any unwanted edges are deleted. This is the branch-set viewpoint on minor models developed in the earlier material on graph minors.
Every Subdivision Is a Minor
Proof. Assume that a subgraph \(S\) of \(G\) is a subdivision of \(H\). For each vertex \(v\) of \(H\), let \(b_v\) be the corresponding branch vertex in \(S\). For each edge \(uv\) of \(H\), its replacing path in \(S\) joins \(b_u\) to \(b_v\). Delete from \(G\) all vertices and edges not in \(S\). On each replacing path, contract every edge except the final edge incident with \(b_v\). This identifies all internal vertices of that path with \(b_u\), leaving an edge from \(b_u\) to \(b_v\). The internal vertices of distinct replacing paths are disjoint, so these contractions do not identify two branch vertices or interfere with one another. If a replacing path has length one, no contraction is needed. Once all paths have been reduced, the remaining edges join exactly the branch vertices corresponding to edges of \(H\). Delete any extra edges between these branch vertices. The resulting graph is isomorphic to \(H\), so \(H\) is a minor of \(G\). If \(H\) has no edges, its subdivision consists only of branch vertices; deleting everything else already gives \(H\). \(\square\)
The proof gives a direct method: keep the branch vertices, delete everything outside the subdivision, and contract away the internal vertices of each replacing path. It does not say that every minor can be obtained this way. A contraction can merge vertices that would have to remain distinct branch vertices in a subdivision.
Worked Example: Contracting a Subdivision of a Triangle
Let \(H\) be the triangle on \(\{a,b,c\}\), with edges \(ab,bc,ca\). Let \(G\) have vertex set \(\{1,2,3,4,5,6\}\) and edge set \(\{12,23,34,45,56,61\}\). This is the cycle \(C_6\). Choose branch vertices \(1,3,5\). The paths \(1,2,3\), \(3,4,5\), and \(5,6,1\) replace \(ab,bc,ca\), respectively. Their internal vertices \(2,4,6\) are distinct, so \(G\) is a subdivision of \(H\).
Contract \(12\), then \(34\), then \(56\). Write \(A\) for the vertex formed from \(1,2\), \(B\) for the vertex formed from \(3,4\), and \(C\) for the vertex formed from \(5,6\). The uncontracted edges are \(23,45,61\), which become \(AB,BC,CA\). Thus the result is precisely the triangle \(H\).
Check: The six original edges consist of the three contracted edges \(12,34,56\) and the three remaining edges \(23,45,61\). Those remaining edges give all three distinct pairs \(AB,BC,CA\), so the resulting simple graph is \(K_3\), as required.
Worked Example: Recovering \(K_4\) from a Subdivision
Let \(H=K_4\), with vertices \(\{a,b,c,d\}\) and edges \(ab,ac,ad,bc,bd,cd\). Construct \(G\) by replacing each edge \(uv\) with the path \(u,x_{uv},v\), using a different new vertex \(x_{uv}\) for each edge. In full, \(V(G)=\{a,b,c,d,x_{ab},x_{ac},x_{ad},x_{bc},x_{bd},x_{cd}\}\), and \(E(G)\) consists of the twelve edges \(ax_{ab},x_{ab}b, ax_{ac},x_{ac}c, ax_{ad},x_{ad}d, bx_{bc},x_{bc}c, bx_{bd},x_{bd}d, cx_{cd},x_{cd}d\). Each replacing path has one internal vertex, and those six internal vertices are distinct.
For each of the six paths, contract its edge incident with the first-listed endpoint: contract \(ax_{ab}, ax_{ac}, ax_{ad}, bx_{bc}, bx_{bd}, cx_{cd}\). The resulting edges, which were not contracted, are \(ab,ac,ad,bc,bd,cd\). They join every pair of distinct vertices in \(\{a,b,c,d\}\), giving \(K_4\).
Check: There are four branch vertices and six edges after contraction: one for each of the six edges \(ab,ac,ad,bc,bd,cd\) of \(K_4\). No pair of branch vertices is missing an edge, and there are no other vertices left in the reduced graph.
Why the Converse Fails
To disprove the converse, it is enough to find \(G\) and \(H\) such that \(G\) has \(H\) as a minor but contains no subdivision of \(H\). A star is useful because the centre of a subdivision of a star must retain all its incident edges. For example, a subdivision of \(K_{1,4}\) must have a branch vertex incident with four distinct edges. Contracting a connected set can create such a vertex even if no original vertex has degree four.
Worked Example: A \(K_{1,4}\) Minor Without a \(K_{1,4}\) Subdivision
Let \(H=K_{1,4}\), the star with centre \(z\) and leaves \(y_1,y_2,y_3,y_4\). Define \(G\) by \(V(G)=\{v_1,v_2,v_3,v_4,x_1,x_2,x_3,x_4\}\) and \(E(G)=\{v_1v_2,v_2v_3,v_3v_4,v_1x_1,v_2x_2,v_3x_3,v_4x_4\}\). Use \(\{v_1,v_2,v_3,v_4\}\) as the branch set for \(z\), and \(\{x_i\}\) as the branch set for \(y_i\), for each \(i\in\{1,2,3,4\}\). The centre branch set is connected, since \(v_1v_2v_3v_4\) is a path. The four leaf branch sets are disjoint from one another and from it. Each is joined to the centre branch set by the edge \(v_ix_i\). Contracting \(v_1v_2,v_2v_3,v_3v_4\) merges the four centre vertices; the four edges to \(x_1,x_2,x_3,x_4\) remain. The result is \(K_{1,4}\), so \(G\) contains \(H\) as a minor.
Now calculate the degrees in \(G\). The vertices \(v_1,v_4\) each have degree \(2\), while \(v_2,v_3\) each have degree \(3\). Each \(x_i\) has degree \(1\). Thus \(\Delta(G)=3\). In any subdivision of \(K_{1,4}\), the branch vertex corresponding to the centre has degree \(4\) within the subdivision: the four replacing paths leave it along four distinct edges. If such a subdivision were a subgraph of \(G\), that branch vertex would have degree at least \(4\) in \(G\), contradicting \(\Delta(G)=3\). Hence \(G\) contains no subdivision of \(K_{1,4}\).
Check: The vertex set has \(8\) vertices and the edge set has \(7\) edges. The four pendant edges \(v_ix_i\) provide the four adjacencies required by the minor model, while the three path edges connect the centre branch set. No vertex has degree \(4\), so none can be the centre branch vertex of a \(K_{1,4}\) subdivision.
A Common Mistake
Wrong calculation: In the \(K_{1,4}\) example, contract \(v_1v_2,v_2v_3,v_3v_4\), observe that the resulting centre has degree \(4\), and conclude that \(G\) contains a subdivision of \(K_{1,4}\).
Correction: Those contractions prove that \(G\) contains a \(K_{1,4}\) minor. They change the graph by merging \(v_1,v_2,v_3,v_4\). A subdivision must occur as a subgraph of the original \(G\), without those vertices being merged. Since every vertex of the original graph has degree at most \(3\), it has no possible degree-\(4\) centre for a \(K_{1,4}\) subdivision. Always distinguish a graph obtained after contractions from a subgraph already present before the contractions.
This distinction matters in planar graph arguments. Deletion and contraction are operations used to form minors, whereas a subdivision is a particular subgraph structure. The implication proved here lets a subdivision certify a minor, but the counterexample shows why the two kinds of containment cannot be substituted for one another without an additional theorem or hypothesis.
Check Your Understanding
For each question, keep separate the operations allowed for minors and the subgraph requirement for subdivisions.
- In the \(C_6\) example, which three edges are contracted to obtain \(K_3\), and which three edges become its edges?
- Explain why internal vertices on replacing paths must be distinct for the contraction argument to preserve all branch vertices.
- Give the four branch sets that form a \(K_{1,4}\) minor model in the final example.
- Why does \(\Delta(G)=3\) rule out a subdivision of \(K_{1,4}\), even though it does not rule out a \(K_{1,4}\) minor?
- State the implication between subdivision containment and minor containment, and explain why the final example rules out its converse.