191.7-Contraction and minorsG/eFig. 1.7.1. Contracting the edge e =ryMore generally, if X is another graph and (V r e V(X)) is apartition of V into connected subsets such that, for any two verticesr,y e X, there is a V-Vy edge in G if and only if ry e E(X), we callMXG an MX and write7 G - MX (Fig. 1.7.2). The sets V, are the branchsets of this Mx. Intuitively, we obtain X from G by contracting everybranch setsbranch set to a single vertex and deleting any parallel edges' or 'loops'that may arise. In infinite graphs, branch sets are allowed to be infinite.For example, the graph shown in Figure 8.1.1 is an MX with X aninfinitestar.VGFig.1.7.2.YG=MX,soXisaminorof YIf Vr = U V is one of the branch sets above and every otherbranch set consists just of a single vertex, we also write G/U for theG/Ugraph X and uu for the vertex r e X to which U contracts, and thinkof the rest of X as an induced subgraph of G. The contraction of asingle edge uu' defined earlier can then be viewed as the special case ofU= (u,u'].Proposition 1.7.1. G is an Mx if and only if X can be obtainedfrom G by a series of edge contractions, i.e. if and only if there aregraphs Go,.-, Gn and edges ei e G, such that Go = G, Gn X, andGi+i = Gi/e; for all i < n.口Proof. Induction on |G| -[X].7 Thus formally, the expression MX-whereMstandsfor‘minor':seebelow-refers to a whole class of graphs, and G = MX means (with slight abuse of notation)that G belongs to this class.1.7 Contraction and minors 19 x y e ve G G/e Fig. 1.7.1. Contracting the edge e = xy More generally, if X is another graph and { Vx | x ∈ V (X) } is a partition of V into connected subsets such that, for any two vertices x, y ∈ X, there is a Vx–Vy edge in G if and only if xy ∈ E(X), we call G an MX and write7 G = MX (Fig. 1.7.2). The sets Vx are the branch MX sets of this MX. Intuitively, we obtain X from G by contracting every branch sets branch set to a single vertex and deleting any ‘parallel edges’ or ‘loops’ that may arise. In infinite graphs, branch sets are allowed to be infinite. For example, the graph shown in Figure 8.1.1 is an MX with X an infinite star. X Y Vx Vz x z G Fig. 1.7.2. Y ⊇ G = MX, so X is a minor of Y If Vx = U ⊆ V is one of the branch sets above and every other branch set consists just of a single vertex, we also write G/U for the G/U graph X and vU for the vertex x ∈ X to which U contracts, and think vU of the rest of X as an induced subgraph of G. The contraction of a single edge uu defined earlier can then be viewed as the special case of U = { u, u }. Proposition 1.7.1. G is an MX if and only if X can be obtained from G by a series of edge contractions, i.e. if and only if there are graphs G0,...,Gn and edges ei ∈ Gi such that G0 = G, Gn X, and Gi+1 = Gi/ei for all i<n. Proof . Induction on |G|−|X|.
7 Thus formally, the expression MX—where M stands for ‘minor’; see below— refers to a whole class of graphs, and G = MX means (with slight abuse of notation) that G belongs to this class.