Testing for the Two Forbidden Minors
Wagner’s criterion turns a planarity question into a question about two specific graphs: \(K_5\) and \(K_{3,3}\). In practice, the positive test is concrete: exhibit connected, disjoint vertex sets that can be contracted to the vertices of one of these graphs. A negative test needs more care. Failing to spot a model is not, by itself, evidence that none exists.
All graphs in this tutorial are finite and simple. A minor of a graph is obtained by deleting vertices, deleting edges, and contracting edges; after a contraction, loops are discarded and parallel edges are reduced to a single edge. A branch set is a nonempty set of vertices. It is connected if the subgraph induced by that set is connected. A model of a graph \(H\) in \(G\) consists of one connected branch set \(B_x\) for each vertex \(x\in V(H)\), such that the branch sets are pairwise disjoint and, whenever \(xy\in E(H)\), at least one edge of \(G\) joins \(B_x\) to \(B_y\). Extra edges between branch sets are allowed.
Why Branch Sets Are the Right Test
Proof. First suppose that \(H\) is obtained from \(G\) by deletions and contractions. Each vertex of the resulting graph represents a nonempty set of original vertices: the vertices identified in forming it. Such a set is connected, because each identification was made by contracting an edge. Different resulting vertices represent disjoint sets. If two resulting vertices are adjacent, an edge between their representing sets survived the operations. Thus these sets give a model of \(H\) in \(G\). Deletions simply mean that some vertices or edges of \(G\) need not be used.
Conversely, suppose branch sets \(B_x\) give a model of \(H\). In each connected subgraph \(G[B_x]\), choose a spanning tree; if \(B_x\) has one vertex, that tree has no edges and needs no contractions. Contract the edges of each chosen tree. Because the branch sets are disjoint, these contractions do not identify vertices from different branch sets. The contracted sets become distinct vertices, and every required edge \(xy\) of \(H\) is present because an edge joined \(B_x\) to \(B_y\). Delete all unused vertices and any unwanted edges. The result is \(H\), so \(H\) is a minor of \(G\). \(\square\)
For a \(K_5\) model, there must be five branch sets and every pair must have an edge between them. For a \(K_{3,3}\) model, there must be three branch sets on each side and every cross-pair must be adjacent; edges within one side are not required. These are separate checks: a model of either graph is enough to show nonplanarity by Wagner’s criterion.
Worked Minor Tests
Worked Example: A Subdivision with a \(K_5\) Minor
Let \(G\) have vertices \(x_1,x_2,x_3,x_4,x_5\) and \(y_{ij}\) for every pair \(1\le i<j\le5\). Its edges are \(x_i y_{ij}\) and \(y_{ij}x_j\) for every such pair. Thus every edge of \(K_5\) has been replaced by a path of length \(2\). Does \(G\) have a \(K_5\) minor?
For each \(i\), take the branch set
Each \(B_i\) is connected: every \(y_{ij}\) in it is adjacent to \(x_i\). The sets are disjoint because each \(y_{ij}\) belongs only to \(B_i\), and each \(x_i\) belongs only to \(B_i\). For every pair \(i<j\), the edge \(y_{ij}x_j\) joins \(B_i\) to \(B_j\). So all ten pairs of the five branch sets are adjacent, as required for a \(K_5\) model.
Equivalently, contract \(x_i y_{ij}\) for every \(i<j\). Each such contraction merges \(y_{ij}\) into \(x_i\), while the edge \(y_{ij}x_j\) becomes an edge from \(x_i\) to \(x_j\). There is one resulting edge for each of the ten pairs of indices. The result is \(K_5\).
Check: there are \(\binom{5}{2}=10\) pairs \(i<j\), and each contributes two edges to \(G\), so \(G\) has \(2\cdot10=20\) edges. After contracting one edge per pair, ten edges remain, one for each pair of the five resulting vertices. Also, \(G\) has no \(K_5\) subgraph: each \(y_{ij}\) has degree \(2\), so only the five \(x_i\) could be vertices of such a subgraph, but no two \(x_i\) are adjacent in \(G\). This shows why looking only for a \(K_5\) subgraph would miss the minor.
Worked Example: Restoring Three Missing Cross-Edges
Let \(G\) have vertices \(u_1,u_2,u_3,v_1,v_2,v_3,x_1,x_2,x_3\). Include the six edges \(u_iv_j\) with \(i\ne j\), and the six edges \(u_ix_i\) and \(x_iv_i\), for \(1\le i\le3\). Does \(G\) have a \(K_{3,3}\) minor?
Use branch sets \(B_{u_i}=\{u_i,x_i\}\) on one side and \(B_{v_j}=\{v_j\}\) on the other. Each \(B_{u_i}\) is connected by the edge \(u_ix_i\). All six sets are nonempty and pairwise disjoint. For \(i\ne j\), the edge \(u_iv_j\) joins \(B_{u_i}\) to \(B_{v_j}\). For \(i=j\), the edge \(x_iv_i\) joins \(B_{u_i}\) to \(B_{v_i}\). Hence all nine cross-pairs are adjacent.
Contract the three edges \(u_1x_1,u_2x_2,u_3x_3\). The three edges \(x_iv_i\) become \(u_iv_i\), restoring the missing diagonal pairs. The six edges \(u_iv_j\) with \(i\ne j\) remain. There are now \(6+3=9\) cross-edges, exactly the nine edges of \(K_{3,3}\), with no within-side edges required.
Check: before contraction, the graph has \(6+6=12\) edges: six with unequal indices and six on the three length-\(2\) paths. The contractions remove three edges and leave nine. Independently, \(K_{3,3}\) has \(3\cdot3=9\) cross-pairs, matching the nine edges just counted. Wagner’s criterion therefore says \(G\) is nonplanar.
Worked Example: Ruling Out Both Minors in \(K_5\) Minus an Edge
Let \(G\) have vertex set \(\{1,2,3,4,5\}\) and edge set \(\{12,13,14,15,23,24,25,34,35\}\); this is \(K_5\) with edge \(45\) omitted. Test for the two forbidden minors.
A \(K_5\) minor needs five nonempty, pairwise disjoint branch sets. Since \(G\) has only five vertices, each branch set would have to be a singleton and together they would use all five vertices. The required adjacency between the branch sets for \(4\) and \(5\) is absent: edge \(45\) is not in \(G\). Thus \(G\) has no \(K_5\) minor.
A \(K_{3,3}\) minor needs six nonempty, pairwise disjoint branch sets. Six such sets cannot be chosen from five vertices, so \(G\) has no \(K_{3,3}\) minor either. By Wagner’s criterion, \(G\) is planar.
One can also verify planarity directly. Draw triangle \(123\); place \(4\) inside it and join \(4\) to \(1,2,3\); place \(5\) outside it and join \(5\) to \(1,2,3\). The two groups of edges lie on opposite sides of the triangle and do not cross. The edge list has \(\binom{5}{2}-1=10-1=9\) edges, independently confirmed by counting its three triangle edges and the six edges from \(4\) and \(5\) to \(\{1,2,3\}\).
What a Failed Search Does—and Does Not—Show
The branch-set test makes the difference between evidence and a proof of absence precise. Finding valid branch sets is a certificate: one can check their disjointness, connectivity and required adjacencies directly. Not finding them by inspection is not a certificate. A search that checks only subgraphs, only some contractions, or only some candidate branch sets can miss a minor.
The first worked example gives a specific warning. It has no \(K_5\) subgraph, but it does have a \(K_5\) minor. A search for five mutually adjacent original vertices fails because the original \(x_i\) are not adjacent to one another. Contracting the paths reveals the missing adjacencies. Thus “I found no \(K_5\) subgraph” does not mean “I found no \(K_5\) minor.”
For a finite graph, an exhaustive search over all possible branch-set choices could establish that no model exists, but the search must genuinely cover every possibility. A failed, non-exhaustive search establishes only that the particular candidates tested did not work. In a hand argument, it is often easier to certify planarity by giving a plane embedding, or to rule out models using a structural restriction such as the number of vertices, as in the third example. Wagner’s criterion then relates a valid absence proof to planarity.
Check Your Understanding
For each question, distinguish a model certificate from an incomplete search.
- In a proposed \(K_5\) model, five disjoint connected branch sets have edges between nine of the ten pairs. Does this certify a \(K_5\) minor? What is missing?
- Why does the graph in the first worked example have no \(K_5\) subgraph, yet have a \(K_5\) minor?
- Suppose a graph has five vertices. Explain why it cannot have a \(K_{3,3}\) minor.
- In the second worked example, which branch-set edge supplies the adjacency between \(u_i\) and \(v_i\) after contraction?
- A manual search checks several possible branch sets and finds no model. What additional fact would be needed to conclude that the graph is planar by Wagner’s criterion?