18 The BasioX-*Fig. 1.6.2. Three drawings of the bipartite graph Ks.3 = K3starcalled stars; the vertex in the singleton partition class of this Ki,n is thecentrestar's centre.odd cycleClearly,abipartitegraph cannotcontainan odd cycle,acycleof oddlength. In fact, the bipartite graphs are characterized by this propertyProposition 1.6.1. A graph is bipartite if and only if it contains noodd cycle.(1.5.1)Proof. Let G- (V.E)be a graph without odd cvcles:we show thatG isbipartite. Clearly a graph is bipartite if all its coonentsarebipartiteor trivial, so we may assume that G is connected. Let T be a spanningtree in G, pick a root r e T, and denote the associated tree-order on Vby <T.For eachu eV,theuniquepathrTuhas odd or even lengthThis defines a bipartition of V; we show that G is bipartite with this partition.Fig. 1.6.3. The cycle Ce in T +e ry be an edge of G. If ee T, with <T y say, therLeterTy = rTry and so + and y lie in different partition classes. If e Tthen Ce := rTy +e is a cycle (Fig. 1.6.3), and by the case treatedalready the vertices along rTy alternate between the two classes. SinceCe is even by assumption, and y again lie in different classes.区
18 1. The Basics = = Fig. 1.6.2. Three drawings of the bipartite graph K3,3 = K2 3 star called stars; the vertex in the singleton partition class of this K1,n is the centre star’s centre. odd cycle Clearly, a bipartite graph cannot contain an odd cycle, a cycle of odd length. In fact, the bipartite graphs are characterized by this property: Proposition 1.6.1. A graph is bipartite if and only if it contains no [1.9.4] [5.3.1] [6.4.2] odd cycle. (1.5.1) Proof. Let G = (V,E) be a graph without odd cycles; we show that G is bipartite. Clearly a graph is bipartite if all its components are bipartite or trivial, so we may assume that G is connected. Let T be a spanning tree in G, pick a root r ∈ T, and denote the associated tree-order on V by T . For each v ∈ V , the unique path rTv has odd or even length. This defines a bipartition of V ; we show that G is bipartite with this partition. e Ce r x y Fig. 1.6.3. The cycle Ce in T + e Let e = xy be an edge of G. If e ∈ T, with x <T y say, then rTy = rT xy and so x and y lie in different partition classes. If e /∈ T then Ce := xT y + e is a cycle (Fig. 1.6.3), and by the case treated already the vertices along xT y alternate between the two classes. Since Ce is even by assumption, x and y again lie in different classes.
191.7Contran andmimo1.7 Contraction and minorsIn Section 1.1 we saw two fundamental containment relations betweengraphs:the'subgraph'relation.and theinduced subgraph'relation. Inthis section we meet two more: the 'minor'relation, and the 'topologicalminor' relation. Let X be a fixed graph.A subdivision of X is, informally, any graph obtained from X by'subdividing'some or all of its edges by drawing new vertices on thosesubdivitoxedges. In other words, we replace some edges of X with new pathsbetween their ends, so that none of these paths has an inner vertex inV(X) or on another new path. When G is a subdivision of X, we alsobranchsaythatGisaTX.7Theoriginal verticesof X arethebranchverticesverticesof the TX:its new vertices are called suhdividing uertices.Note thatsubdividing vertices have degree 2, while branch vertices retain theirdegree from XIf a graph Y contains a TX as a subgraph, then X is a topologicalopoogicalminor of Y(Fig.1.7.1).mV1-国-<Fig. 1.7.1. The graph G is a TX, a subdivision of XAs GCY,this makes X a topoloqical minor of YSimilarly.replacing the vertices of X with disjoint connectedgraphs Ga, and the edges ry of X with non-empty sets of Ga-Gy edges,yields a graph that we shall call an Ix.8 More formally, a graph G isan IX if its vertex set admits a partition (V, [r e V(X)) into con-IXnected subsets V, such that distinct vertices ,y e X are adjacent in Xif and onlyif G contains a V.-V.edge.The sets V.arethe branch setsbranch setsof the IX, Conversely, we say that X arises from G by contracting thentractionminorofy.contractionsubgraphs G and call it a conIf a graphY contains an IX as a subgraph, then X is a minor ofY,minor,the IX is a model of X in Y, and we write X Y (Fig. 1.7.2)modelTheT'standsfortologicalAltof graphs, the class of all subdivisions of X, it is customary to use the expression asindicated to refer to an arbitrary member of that class.8 The 'T' stands for inflated'. As before, while IX is formally a class of graphsthose admittartition (V / e V(X)) as described below, weusetheas indicated to refertoarbitrarymember of that clasexpres
1.7 Contraction and minors 19 1.7 Contraction and minors In Section 1.1 we saw two fundamental containment relations between graphs: the ‘subgraph’ relation, and the ‘induced subgraph’ relation. In this section we meet two more: the ‘minor’ relation, and the ‘topological minor’ relation. Let X be a fixed graph. A subdivision of X is, informally, any graph obtained from X by ‘subdividing’ some or all of its edges by drawing new vertices on those edges. In other words, we replace some edges of X with new paths subdivision TX of X between their ends, so that none of these paths has an inner vertex in V (X) or on another new path. When G is a subdivision of X, we also say that G is a TX. 7 The original vertices of X are the branch vertices branch vertices of the TX; its new vertices are called subdividing vertices. Note that subdividing vertices have degree 2, while branch vertices retain their degree from X. If a graph Y contains a TX as a subgraph, then X is a topological minor of Y (Fig. 1.7.1). topological minor X G Y Fig. 1.7.1. The graph G is a TX, a subdivision of X. As G ⊆ Y , this makes X a topological minor of Y . Similarly, replacing the vertices x of X with disjoint connected graphs Gx, and the edges xy of X with non-empty sets of Gx– Gy edges, yields a graph that we shall call an IX. 8 More formally, a graph G is an IX if its vertex set admits a partition { Vx | x ∈ V (X) } into con- IX nected subsets Vx such that distinct vertices x, y ∈ X are adjacent in X if and only if G contains a Vx–Vy edge. The sets Vx are the branch sets branch sets of the IX. Conversely, we say that X arises from G by contracting the subgraphs Gx and call it a contraction minor of Y . contraction If a graph Y contains an IX as a subgraph, then X is a minor of Y, minor, the IX is a model of X in Y, and we write X Y (Fig. 1.7.2). model 7 The ‘T’ stands for ‘topological’. Although, formally, TX denotes a whole class of graphs, the class of all subdivisions of X, it is customary to use the expression as indicated to refer to an arbitrary member of that class. 8 The ‘I’ stands for ‘inflated’. As before, while IX is formally a class of graphs, those admitting a vertex partition { Vx | x ∈ V (X) } as described below, we use the expression as indicated to refer to an arbitrary member of that class.
201. The BasicThuisX isaminorof Yif and onlyif thereisamapofromasubset of V(Y) onto V(X) such that for every vertex e X its inverseimage o-1() is connected in Y and for every edge rae X there is anedge in Y between the branch sets -1() and p-1(r) of its ends. Ifthe dorain of (p is all of V(Y), and ra' e X whenever arandYhasanedgebetwm p-1(r) and p-i(r') (so that Y is an IX), we call acontraction contraction of Y onto X.Since branch sets can be singletons,every subgraph of a graph isalso its minor. In infinite graphs, branch sets are allowed to be infinite.For example, the graph shown in Figure 8.1.1 is an IX with X an infinitestar.一GFig.1.7.2.Thegraph G is a model of X inY,whichmakesXaminor ofY.Proposition 1.7.1. The minor relation and the topological-minor[12.6.1]relation are partialorderings on the class of finite graphs, ie they arerefexive, antisymmetric and transitive.厦If G is an IX, then P = [V. | r e X ) is a partition of V(G), and weG/Pwrite X =: G/P for this contraction minor of G. If U - V, is the onlyG/Unon-singleton branch set, we write X =: GJU, write vu for the vertexDU eX towhich U contracts, and think of the rest of X as an inducedsubgraph of G. The 'smallest'non-trivial case of this is that U containsexactly two vertices forming an edge e, so that U = e. We then say thatctinarmyontratnthgeeFiguan edgeGleFig. 1.7.3. Contracting the edge e - ry
20 1. The Basics Thus, X is a minor of Y if and only if there is a map ϕ from a subset of V (Y ) onto V (X) such that for every vertex x ∈ X its inverse image ϕ−1(x) is connected in Y and for every edge xx ∈ X there is an edge in Y between the branch sets ϕ−1(x) and ϕ−1(x ) of its ends. If the domain of ϕ is all of V (Y ), and xx ∈ X whenever x = x and Y has an edge between ϕ−1(x) and ϕ−1(x ) (so that Y is an IX), we call ϕ a contraction contraction of Y onto X. Since branch sets can be singletons, every subgraph of a graph is also its minor. In infinite graphs, branch sets are allowed to be infinite. For example, the graph shown in Figure 8.1.1 is an IX with X an infinite star. X Y Vx Vz x z G Fig. 1.7.2. The graph G is a model of X in Y, which makes X a minor of Y. [12.6.1] Proposition 1.7.1. 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. If G is an IX, then P = { Vx | x ∈ X } is a partition of V (G), and we G/P write X =: G/P for this contraction minor of G. If U = Vx is the only G/U non-singleton branch set, we write X =: G/U, write vU for the vertex vU x ∈ X to which U contracts, and think of the rest of X as an induced subgraph of G. The ‘smallest’ non-trivial case of this is that U contains exactly two vertices forming an edge e, so that U = e. We then say that X = G/e arises from G by contracting the edge e; see Figure 1.7.3. contracting an edge x y e ve G G/e Fig. 1.7.3. Contracting the edge e = xy
211.7 Conndmimction istransitive,everyceofsinglevertexquenor edge deletions or contractions yields a minor. Conversely, every minorof a given finite graph can be obtained in this way:Corollary 1.7.2. Let X and Y be finite graphs. X is a minor of Y ifand only if there aregraphs Go...Gn such that Go-Y and Gn -Xand each Gi+1 arises from G, by deleting an edge, contracting an edge,or deleting a vertex.口Proof. Induction on [YI+ [YFinally, we have the following relationship between minors and to.pological minors:134Proposition 1.7.3.(i) Every TX is also an IX (Fig. 1.7.4); thus, every topological minor[12.7.3]of a graph is also its (ordinary) minor.(i) If A(X) ≤ 3, then every IX contains a TX; thus, every minorwith maximum degree at most 3 of a graph is also its topologicalminor.口Fig. 1.7.4. A subdivision of K4 viewed as an IK4t we have met all the stanandard relations between graphsNowthatalso define what it means to embed one graph in another. Bacally, an embedding of G in H is an injective map p: V(G)- V(H) thatembeddingpreserves the kind of structure we are interested in. Thus, p embeds Gin H 'as a subgraph' if it preserves the adjacency of vertices, and as aninduced subgraph' if it preserves both adjacency and non-adjacency. Ifp is defined on E(G) as well as on V(G) and maps the edges ry of G toindependent paths in H between () and p(y), it embeds G in H 'asminorSimilarly,an embeddingpofGinHaatogcawouldbeamapfromV(G)to disjointconnecinH (rathevertexthan to single vertices) so that H has an edge between the sets (p(r) and(y) whenever ry is an edge of G. Further variants are possible; depend-ing on the context, one may wish to define embeddings as a spanningsubgraph', 'as an induced Dr and so on,in the obviousway
1.7 Contraction and minors 21 Since the minor relation is transitive, every sequence of single vertex or edge deletions or contractions yields a minor. Conversely, every minor of a given finite graph can be obtained in this way: Corollary 1.7.2. Let X and Y be finite graphs. X is a minor of Y if and only if there are graphs G0,...,Gn such that G0 = Y and Gn = X and each Gi+1 arises from Gi by deleting an edge, contracting an edge, or deleting a vertex. Proof. Induction on |Y | + Y . Finally, we have the following relationship between minors and topological minors: Proposition 1.7.3. [4.4.2] [7.3.1] [12.7.3] (i) Every TX is also an IX (Fig. 1.7.4); thus, every topological minor of a graph is also its (ordinary) minor. (ii) If Δ(X) 3, then every IX contains a TX; thus, every minor with maximum degree at most 3 of a graph is also its topological minor. Fig. 1.7.4. A subdivision of K4 viewed as an IK4 Now that we have met all the standard relations between graphs, we can also define what it means to embed one graph in another. Basically, an embedding of G in H is an injective map ϕ: V (G)→V (H) that embedding preserves the kind of structure we are interested in. Thus, ϕ embeds G in H ‘as a subgraph’ if it preserves the adjacency of vertices, and ‘as an induced subgraph’ if it preserves both adjacency and non-adjacency. If ϕ is defined on E(G) as well as on V (G) and maps the edges xy of G to independent paths in H between ϕ(x) and ϕ(y), it embeds G in H ‘as a topological minor’. Similarly, an embedding ϕ of G in H ‘as a minor’ would be a map from V (G) to disjoint connected vertex sets in H (rather than to single vertices) so that H has an edge between the sets ϕ(x) and ϕ(y) whenever xy is an edge of G. Further variants are possible; depending on the context, one may wish to define embeddings ‘as a spanning subgraph’, ‘as an induced minor’ and so on, in the obvious way.
221. The Basics1.8 Euler toursAny mathematician who happens to find himself in the East Prussiancity of Konigsberg (and in the 18th century) will lose no time to follow thegreat Leonhard Euler's example and inquire about a round trip throughthe old city that traverses each of the bridges shown in Figure 1.8.1exactly once意S精装5ENyeseFig. 1.8.1. The bridges of Konigsberg (anno 1736)Thus inspiredlet us calla closed walk in agraph an Euler tourifEulerianit traverses every edge of the graph exactly once. A graph is Eulerian ifit admits an Euler tour.Fig.1.8.2.A graph formalizing the bridge problem[0.5.]Theorem 1.8.1. (Euler 1736)A connected graph is Eulerian if and only if every vertenandegree9 Anyone to whom such inspiration seems far-fetched,even after contemplatingFigure1.8.2,mayseek consolationinthemultigraphof Figure1.10.1
22 1. The Basics 1.8 Euler tours Any mathematician who happens to find himself in the East Prussian city of K¨onigsberg (and in the 18th century) will lose no time to follow the great Leonhard Euler’s example and inquire about a round trip through the old city that traverses each of the bridges shown in Figure 1.8.1 exactly once. Fig. 1.8.1. The bridges of K¨onigsberg (anno 1736) Thus inspired,9 let us call a closed walk in a graph an Euler tour if Eulerian it traverses every edge of the graph exactly once. A graph is Eulerian if it admits an Euler tour. Fig. 1.8.2. A graph formalizing the bridge problem Theorem 1.8.1. (Euler 1736) [2.1.5] [10.3.1] A connected graph is Eulerian if and only if every vertex has even degree. 9 Anyone to whom such inspiration seems far-fetched, even after contemplating Figure 1.8.2, may seek consolation in the multigraph of Figure 1.10.1