What Is a Graph Minor?
Deleting parts of a graph can only remove structure, while contracting an edge can combine two adjacent vertices into one. Together, these operations define a useful way to compare graphs: one graph is a minor of another if it can be obtained by a finite sequence of these operations. A second description uses connected sets of vertices in the original graph. These sets, called branch sets, record which parts of the original graph represent the vertices of the minor.
Throughout, graphs are finite and simple. If an edge \(uv\) is contracted, its endpoints are identified as one vertex; loops created by the identification are removed, and any parallel edges are replaced by a single edge. The result is therefore again a simple graph. Deleting a vertex also deletes all edges incident with it. Each operation may be applied zero or more times, and a graph is allowed to have no vertices.
The definition imposes no requirement that an operation must be used. In particular, every graph is a minor of itself. Isolated vertices can be retained, deleted, or represented in a minor model, depending on the desired graph.
Branch Sets
Connected means that every pair of vertices in the set can be joined by a path using vertices of that set. A one-vertex set is connected. The edge condition is one-way: every edge required by \(H\) must be represented, but an extra edge between branch sets is allowed. Such an edge may simply be deleted when carrying out the operations.
Proof. First suppose that \(H\) is obtained from \(G\) by a sequence of the allowed operations. Track, for each vertex currently present, the set of original vertices of \(G\) that have been combined to form it. Initially each such set is a singleton. These sets are pairwise disjoint. Deleting a vertex removes its set, and deleting an edge does not change any set. Contracting an edge between two current vertices merges their sets. The original sets were connected, and an original edge joined them because the contracted edge was present; therefore their union is connected in \(G\). Thus every vertex remaining at the end corresponds to a nonempty connected set, and these sets are disjoint. Each edge remaining at the end comes from an original edge between the corresponding sets. In particular, every edge of \(H\) has the required edge between its branch sets. This gives a branch-set model.
Conversely, suppose branch sets \(B_x\) give a model of \(H\). For each \(x\), choose edges within \(G[B_x]\) that connect all its vertices and contain no cycle. Such a set of edges can be obtained by starting with no edges and adding an edge between already separate components until the selected edges connect the set; adding an edge between separate components cannot create a cycle. Contract these selected edges within each branch set. Each \(B_x\) is now represented by one vertex, and disjointness ensures the contractions do not merge different branch sets. For every edge \(xy\) of \(H\), retain one edge between \(B_x\) and \(B_y\), which exists by the model condition. Delete all vertices outside the branch sets and all other edges. The resulting simple graph has exactly the vertices and edges of \(H\), up to their labels. If \(H\) is empty, the model has no branch sets and deleting all vertices of \(G\) gives \(H\). Thus \(H\) is a minor of \(G\). \(\square\)
The theorem gives two complementary ways to check a claim. A sequence of operations explicitly constructs the minor. A branch-set model specifies, inside the original graph, which connected pieces will become its vertices. The latter is often shorter to verify because it does not require writing every intermediate graph.
Worked Models
Worked Example: A \(K_4\) Minor from Six Vertices
Let \(G\) have vertex set \(\{a_1,a_2,b,c_1,c_2,d\}\) and edge set \(\{a_1a_2,c_1c_2,a_1b,a_2c_1,a_2d,bc_1,bd,c_2d\}\). We show that \(G\) contains \(K_4\) as a minor.
Assign branch sets \(B_A=\{a_1,a_2\}\), \(B_B=\{b\}\), \(B_C=\{c_1,c_2\}\), and \(B_D=\{d\}\). The sets are nonempty and pairwise disjoint. The induced graph on \(B_A\) contains \(a_1a_2\), so it is connected; the induced graph on \(B_C\) contains \(c_1c_2\), so it is connected. The singleton sets are connected as well.
Check all six pairs of branch sets, since \(K_4\) has an edge between every pair of its four vertices. \(B_A,B_B\) are joined by \(a_1b\); \(B_A,B_C\) by \(a_2c_1\); \(B_A,B_D\) by \(a_2d\); \(B_B,B_C\) by \(bc_1\); \(B_B,B_D\) by \(bd\); and \(B_C,B_D\) by \(c_2d\). Every required pair is joined, so these are branch sets for a \(K_4\) minor.
Check: Contract \(a_1a_2\) and \(c_1c_2\). The six listed cross-set edges become the six distinct edges between the four resulting vertices. Since \(\binom{4}{2}=4\cdot3/2=6\), this is exactly \(K_4\). The original graph has \(2+6=8\) edges: two within branch sets and six between them.
Worked Example: A \(K_{2,3}\) Minor
Let \(G\) have vertex set \(\{p,x,q,y,r,s,t\}\) and edge set \(\{px,qy,pr,ps,pt,qr,qs,qt\}\). We seek a \(K_{2,3}\) minor, whose two parts have sizes two and three.
Use branch sets \(B_P=\{p,x\}\), \(B_Q=\{q,y\}\), \(B_R=\{r\}\), \(B_S=\{s\}\), and \(B_T=\{t\}\). The first two sets are connected because \(px\) and \(qy\) are edges; the other three are singletons. They are pairwise disjoint. The required edges from the two-vertex part to the three-vertex part are represented by \(pr,ps,pt,qr,qs,qt\), respectively. These are all six required edges, so the sets form a model of \(K_{2,3}\).
Contract \(px\) and \(qy\). The resulting vertices are represented by \(\{p,x\}\), \(\{q,y\}\), \(\{r\}\), \(\{s\}\), and \(\{t\}\). The six edges between the two larger-part vertices and the three singleton vertices remain. There are no edges within either part in the listed edge set, so the result is \(K_{2,3}\).
Check: \(K_{2,3}\) has \(2\cdot3=6\) edges. Its two vertices in the size-two part each have degree \(3\), and its three vertices in the size-three part each have degree \(2\). The degree sum is \(3+3+2+2+2=12=2\cdot6\), consistent with the six edges obtained.
Worked Example: Contracting a Cycle Edge to Obtain a Triangle
Let \(G\) have vertex set \(\{1,2,3,4\}\) and edge set \(\{12,23,34,41\}\). Let \(H=K_3\), with vertices \(A,B,C\) and edges \(AB,BC,CA\). Define \(B_A=\{1,2\}\), \(B_B=\{3\}\), and \(B_C=\{4\}\).
The sets are disjoint and nonempty. \(G[B_A]\) is connected because it contains \(12\), and \(B_B,B_C\) are singletons. The edge \(23\) joins \(B_A\) to \(B_B\), \(34\) joins \(B_B\) to \(B_C\), and \(41\) joins \(B_C\) to \(B_A\). These are exactly the three pairs required for \(K_3\).
Contract \(12\), producing one vertex from \(\{1,2\}\). The edges \(23\), \(34\), and \(41\) then join the three resulting vertices in pairs. Thus the result has edges \(AB,BC,CA\), which is \(K_3\).
Check: the original graph has four edges. One, \(12\), is contracted; the other three become the three edges of the triangle. The resulting edge count is \(4-1=3\), agreeing with \(\binom{3}{2}=3\).
Minor Operations Can Be Chained
Proof. Since \(H\) is a minor of \(G\), there is a finite sequence of vertex deletions, edge deletions, and edge contractions that transforms \(G\) into a graph isomorphic to \(H\). Since \(J\) is a minor of \(H\), there is another such finite sequence transforming \(H\) into a graph isomorphic to \(J\). Apply the first sequence and then the second, identifying the intermediate graph with \(H\) by its isomorphism. The concatenated sequence uses only allowed operations and produces a graph isomorphic to \(J\). Hence \(J\) is a minor of \(G\). This reasoning also applies if one of the graphs is empty or if either sequence has no operations. \(\square\)
This transitivity is useful when a graph is simplified in stages: once a minor has been obtained, any minor of that graph is also a minor of the original. It does not mean that every pair of branch-set models can simply be treated as a single model without checking how their vertex sets combine; the operation-based definition guarantees the conclusion.
Common Pitfalls
Requiring nonadjacent branch sets to have no edge between them is too strict. For example, let \(G=K_3\) with vertex set \(\{1,2,3\}\) and edge set \(\{12,23,13\}\). To model the path \(P_3\), whose vertices are \(A,B,C\) and whose edges are \(AB,BC\), take \(B_A=\{1\}\), \(B_B=\{2\}\), and \(B_C=\{3\}\). The edges \(12\) and \(23\) represent the two required edges. The extra edge \(13\) does not invalidate the model: delete it to obtain \(P_3\).
A wrong check would say, “\(A\) and \(C\) are not adjacent in \(P_3\), but \(13\) joins their branch sets, so this is not a model.” The correction is that the definition requires edges for adjacent pairs in the target and places no restriction on other pairs. The three singleton sets are connected and disjoint, and both required edges exist, so the model is valid.
Connectedness applies within each branch set. Two disconnected pieces cannot represent one minor vertex merely because each piece has edges to other branch sets. If a proposed set is disconnected, it cannot be contracted to a single vertex using edges within that set. Check nonemptiness, pairwise disjointness, and connectedness before checking the target edges.
Check Your Understanding
For each question, distinguish the properties required of branch sets from the edges required by the target graph.
- Let \(G\) have vertices \(\{1,2,3,4\}\) and edges \(\{12,23,34\}\). Give branch sets for a \(P_3\) minor, or explain why none exist.
- In a branch-set model of \(K_4\), how many pairs of branch sets must be joined by edges of the original graph?
- Why is a singleton branch set connected even if its vertex has degree zero?
- Suppose a proposed model has disjoint connected branch sets and all target edges are represented, but two nonadjacent target vertices also have an edge between their branch sets. Is the model valid? Explain.
- Explain how the branch-set characterization handles the empty target graph.