201.The BasicsIfG= MX is a subgraph of another graph Y, we call X a minor of Yand write X Y. Note that every subgraph of a graph is also its minor;minor;人in particular, every graph is its own minor. By Proposition 1.7.1, anyminor of a graph can be obtained from it by first deleting some verticesand edges, and then contracting some further edges. Conversely, anygraph obtained from another by repeated deletions and contractions (inany order) is its minor: this is clear for one deletion or contraction, andfollows for several from the transitivity of the minor relation (Proposition1.7.3).If we replace the edges of X with independent paths between theirends (so that none of these paths has an inner vertex on another pathsubdivisionor in X), we call the graph G obtained a subdivision of X and writeTXG = TX's If G = TX is the subgraph of another graph Y, then X is atopologicaltopological minor of Y (Fig. 1.7.3).minorFig. 1.7.3. Y 2 G = TX, so X is a topological minor of YIf G = TX, we view V(X) as a subset of V(G) and call these verticesbranchthe branch vertices of G; the other vertices of G are its subdividingverticesvertices.Thus, all subdividing vertices have degree 2, while the branchvertices retain their degree from X.[4.4.2]Proposition 1.7.2.7.3.1][12.5.3](i) Every TX is also an MX (Fig. 1.7.4); thus, every topologicalminor of a graph is also its (ordinary) minor.(i) If △(X) ≤ 3, then every MX contains a TX; thus, every minorwith maximum degree at most 3 of a graph is also its topological口minor.Proposition 1.7.3. The minor relation ≤ and the topological-minor[12.4.1]relation are partial orderings on the class of finite graphs, i.e. they are口reflexive, antisymmetric and transitive.8 So again TX denotes an entire class of graphs: all those which, viewed as atopological space in the obvious way, are homeomorphic to X.The T in TX standsfor‘topological".20 1. The Basics If G = MX is a subgraph of another graph Y , we call X a minor of Y minor;
and write X  Y . Note that every subgraph of a graph is also its minor; in particular, every graph is its own minor. By Proposition 1.7.1, any minor of a graph can be obtained from it by first deleting some vertices and edges, and then contracting some further edges. Conversely, any graph obtained from another by repeated deletions and contractions (in any order) is its minor: this is clear for one deletion or contraction, and follows for several from the transitivity of the minor relation (Proposition 1.7.3). If we replace the edges of X with independent paths between their ends (so that none of these paths has an inner vertex on another path or in X), we call the graph G obtained a subdivision of X and write subdivision T X G = T X. 8 If G = T X is the subgraph of another graph Y , then X is a topological minor of Y (Fig. 1.7.3). topological minor X Y G Fig. 1.7.3. Y ⊇ G = T X, so X is a topological minor of Y If G = T X, we view V (X) as a subset of V (G) and call these vertices the branch vertices of G; the other vertices of G are its subdividing branch vertices vertices. Thus, all subdividing vertices have degree 2, while the branch vertices retain their degree from X. Proposition 1.7.2. [ 4.4.2 ] [ 7.3.1 ] [ 12.5.3 ] (i) Every T X is also an MX (Fig. 1.7.4); thus, every topological minor of a graph is also its (ordinary) minor. (ii) If ∆(X) 3, then every MX contains a T X; thus, every minor with maximum degree at most 3 of a graph is also its topological minor.
[ 12.4.1 ] Proposition 1.7.3. The minor relation  and the topological-minor relation are partial orderings on the class of finite graphs, i.e. they are reflexive, antisymmetric and transitive.
8 So again T X denotes an entire class of graphs: all those which, viewed as a topological space in the obvious way, are homeomorphic to X. The T in T X stands for ‘topological’.