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’.
211.7 Contraction and minorsFig.1.7.4. A subdivision of K* viewed as an MK4Now that we have met all the standard relations between graphs.we can also define what it means to embed one graph in another. Basi-cally, an embedding of G in H is an injective map o:V(G)V(H) thatembeddingpreserves the kind of structure we are interested in. Thus, embeds Gin H 'as a subgraph' if it preserves the adjacency of vertices, and 'asan 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 ryof G to independent paths in H between p(r) and p(y), it embeds Gin H 'as a topological minor'. Similarly, an embedding y of G in H asaminorwould beamapfromV(G)todisjoint connected vertex setsin H (rather than to single vertices) such that H has an edge betweenthe sets () and (y) whenever ry is an edge of G. Further variants arepossible; depending on the context, one may wish to define embeddingsasaspanningsubgraph',‘asaninduced minor'and so on in theobivousway.1.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.Thus inspired.9 let us call a closed walk in a graph an Euler tour ifit traverses every edge of the graph exactly once. A graph is Eulerian ifEulerianitadmitsanEulertour(16.]Theorem 1.8.1. (Euler 1736)A connected graph is Eulerian if and only if every vertex has even degreeProof.The degree condition is clearly necessary: a vertex appearing ktimes in an Euler tour (or k+1 times, if it is the starting and finishingvertex and as such counted twice) must have degree 2k.9 Anyoneto whom suchinspirationseeaftercontemplatingms far-fetchedFigure 1.8.2, may seek consolation in the multigraph of Figure 1.10.1
1.7 Contraction and minors 21 Fig. 1.7.4. A subdivision of K4 viewed as an MK4 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) such 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 obivous way. 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. Thus inspired,9 let us call a closed walk in a graph an Euler tour if it traverses every edge of the graph exactly once. A graph is Eulerian if Eulerian it admits an Euler tour. Theorem 1.8.1. (Euler 1736) [ 2.1.5 ] [ 10.3.3 ] A connected graph is Eulerian if and only if every vertex has even degree. Proof . The degree condition is clearly necessary: a vertex appearing k times in an Euler tour (or k + 1 times, if it is the starting and finishing vertex and as such counted twice) must have degree 2k. 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
22The数漫encaseThebridges of Konigsberg (anno1736)Fig.1.8.1.Conversely, let G be a connected graph with all degrees even, andletW= voeo...et-1vebe a longest walk in G usingno edge more than once.Since W cannotbe extended, it already contains all the edges at ve. By assumption, thenumber of such edges is even. Hence ve = vo, so W is a closed walkSuppose W is not an Euler tour. Then G has an edge e outside Wbut incident with a vertex of W, say e = ww. (Here we use the connect-edness of G.asintheproof of Proposition1.4.1.)Then thewalkueviei...e-iveeo..ei-ui口is longer than W, a contradiction.Fig.1.8.2.A graph formalizing the bridge problem
22 1. The Basics Fig. 1.8.1. The bridges of K¨onigsberg (anno 1736) Conversely, let G be a connected graph with all degrees even, and let W = v0e0 ...e−1v be a longest walk in G using no edge more than once. Since W cannot be extended, it already contains all the edges at v. By assumption, the number of such edges is even. Hence v = v0, so W is a closed walk. Suppose W is not an Euler tour. Then G has an edge e outside W but incident with a vertex of W, say e = uvi. (Here we use the connectedness of G, as in the proof of Proposition 1.4.1.) Then the walk ueviei ...e−1ve0 ...ei−1vi is longer than W, a contradiction. Fig. 1.8.2. A graph formalizing the bridge problem
231.9. Some linear algebra1.9 Some linear algebraLet G = (V,E) be a graph with n vertices and m edges, say VG =(V,E)[ ui,.., un ] and E - [ei,..,em ]. The verter space V(G) of G is thevector space over the 2-element field F2 = [0, 1 ] of all functions V- F2(space V(G)Every element of V(G) corresponds naturally to a subset of V, the set ofthose vertices to which it assigns a l, and every subset of V is uniquelyrepresented in v(G) by its indicator function. We may thus think ofV(G) as the power set of V made into a vector space: the sum U + U+of two vertex sets U,U' V is their symmetric difference (why?), andU = -U for all U C V. The zero in V(G), viewed in this way, is theempty (vertex) set 0. Since ((ui),..,( un)) is a basis of V(G), itsstandard basis, we have dim V(G) = nIn the same way as above, the functions E -→ F2 form the edgeedge spacspace E(G) of G: its elements are the subsets of E, vector additionE(G)amounts to sysymmetric difference, 0 C E is the zero, and F--F forstandardall FC E. As before, ((ei ).., em J) s the standard basis of e(G),basisand dimE(G) = m.Since the edges of a graph carry its essential structure, we shallmostly be concerned with the edge space. Given two edge sets F, F'e(G) and their coeficients Ai,.,Am and X'...,'m with respect to thestandard basis, we write(F, F") := AiAi+...+AmAm eF2.(F,F")Note that (F, F") = 0 may hold even when F = F' + 0::indeed,(F,F') = O if and only if F and F' have an even number of edgesin common. Given a subspace F of e(G), we writeFLF+ := [D e E(G) I (F, D) = 0 for all F e F) .This is again a subspace of (G) (the space of all vectors solving a certainset of linear equations-which?), and we have(t)dimF+dimF+=m.cycle spaceThe cycle space C = C(G) is the subspace of e(G) spanned by all"C(G)the cycles in G-more precisely, by their edge sets.10 The dimension ofC(G) is sometimes called the cyclomatic number of G.Proposition 1.9.1. The induced cycles in G generate its entire cycle[3.2.3]space.10Forsmplicity, weshalnotalwaysdistinguish betweentheedge sets Fe(G)and the subgraphs (V,F) they induce in G. When we wish to be more precise, suchas in Chapter 8.5, we shall use the word ‘circuit'for the edge set of a cycle
1.9. Some linear algebra 23 1.9 Some linear algebra Let G = (V,E) be a graph with n vertices and m edges, say V = G = (V,E) { v1,...,vn } and E = { e1,...,em }. The vertex space V(G) of G is the vector space over the 2-element field F2 = { 0, 1 } of all functions V →F2. vertex space V(G) Every element of V(G) corresponds naturally to a subset of V , the set of those vertices to which it assigns a 1, and every subset of V is uniquely represented in V(G) by its indicator function. We may thus think of V(G) as the power set of V made into a vector space: the sum U + U + of two vertex sets U, U ⊆ V is their symmetric difference (why?), and U = −U for all U ⊆ V . The zero in V(G), viewed in this way, is the empty (vertex) set ∅. Since { { v1 },..., { vn } } is a basis of V(G), its standard basis, we have dim V(G) = n. In the same way as above, the functions E → F2 form the edge space E(G) of G: its elements are the subsets of E, vector addition edge space E(G) amounts to symmetric difference, ∅ ⊆ E is the zero, and F = −F for all F ⊆ E. As before, { { e1 },..., { em } } is the standard basis of E(G), standard basis and dim E(G) = m. Since the edges of a graph carry its essential structure, we shall mostly be concerned with the edge space. Given two edge sets F, F ∈ E(G) and their coefficients λ1,...,λm and λ 1,...,λ m with respect to the standard basis, we write F, F := λ1λ 1 + ... + λmλ m ∈ F2 . F, F Note that F, F = 0 may hold even when F = F = ∅: indeed, F, F = 0 if and only if F and F have an even number of edges in common. Given a subspace F of E(G), we write F⊥ := D ∈ E(G) | F, D = 0 for all F ∈ F . F⊥ This is again a subspace of E(G) (the space of all vectors solving a certain set of linear equations—which?), and we have dim F + dim F⊥ = m . (†) The cycle space C = C(G) is the subspace of E(G) spanned by all cycle space C(G) the cycles in G—more precisely, by their edge sets.10 The dimension of C(G) is sometimes called the cyclomatic number of G. Proposition 1.9.1. The induced cycles in G generate its entire cycle [ 3.2.3 ] space. 10 For simplicity, we shall not always distinguish between the edge sets F ∈ E(G) and the subgraphs (V,F) they induce in G. When we wish to be more precise, such as in Chapter 8.5, we shall use the word ‘circuit’ for the edge set of a cycle.
241.The BasicsProof.By definition of C(G) it suffices to show that the induced cyclesin G generate every cycle C C G with a chord e. This follows at onceby induction on JCl: the two cycles in C +e that have e but no otheredge in common are shorter than C, and their symmetric diference isprecisely C.国The elements of C are easily recognized by the degrees of the sub.graphs they form. Moreover, to generate the cycle space from cycles weonly need disjoint unions rather than arbitrary symmetric differences:[4.5.1]Proposition 1.9.2. The following assertions are equivalent for edge setsFCE:(i) F E C(G):(i) F is a disjoint union of (edge sets of) cycles in G;(ii) All vertex degrees of the graph (V, F) are even.Proof. Since cycles have even degrees and taking symmetric differencepreserves this, (i)(ii) follows by induction on the number of cycles usedto generate F. The implication (ii)-(i) follows by induction on F:if F + 0 then (V, F) contains a cycle C, whose edges we delete for theinduction step.Theimplication (i)-(i) is immediatefrom thedefinitionof c(G).口If (Vi, V2) is a partition of V, the set E(Vi, V2) of all the edgesof G crossing this partition is called a cut (or cocycle). Recall that forcutVi = (v) this cut is denoted by E(u).[4.6.3]Proposition 1.9.3. Together with 0, the cuts in G form a subspace C*of E(G). This space is generated by cuts of the form E(u)Proof.Let C*denotethe setof all cuts in G.togetherwith 0.Toprovethat c* is a subspace, we show that for all D,D' eEc* also D+D(= D- D') lies in ct. Since D+ D = O e C* and D+ 0 = D e C*we may assume that D and D' are distinct and non-empty.Let[Vi, V2] and [Vi.V)] be the corresponding partitions of V. ThenD + D' consists of all the edges that cross one of these partitions butnot theother(Fig.1.9.1).Butthese are preciselythe edges betweer(VinV)u(V2nVi) and (VinV)u(V2nvi), and by D + D' these twosets form another partition of V. Hence D+ D' e C*, and c* is indeeda subspace of (G),Our second assertion, that the cuts E(u) generate all of c*,followsfrom the fact that every edge y e G lies in exactly two such cuts (in E(r)and in E(y); thus every partition [V, V2] of V satisfies E(Vi, V2) -AEvev E(u)
24 1. The Basics Proof . By definition of C(G) it suffices to show that the induced cycles in G generate every cycle C ⊆ G with a chord e. This follows at once by induction on |C|: the two cycles in C + e that have e but no other edge in common are shorter than C, and their symmetric difference is precisely C. The elements of C are easily recognized by the degrees of the subgraphs they form. Moreover, to generate the cycle space from cycles we only need disjoint unions rather than arbitrary symmetric differences: [ 4.5.1 ] Proposition 1.9.2. The following assertions are equivalent for edge sets F ⊆ E: (i) F ∈ C(G); (ii) F is a disjoint union of (edge sets of) cycles in G; (iii) All vertex degrees of the graph (V,F) are even. Proof . Since cycles have even degrees and taking symmetric differences preserves this, (i)→(iii) follows by induction on the number of cycles used to generate F. The implication (iii)→(ii) follows by induction on |F|: if F = ∅ then (V,F) contains a cycle C, whose edges we delete for the induction step. The implication (ii)→(i) is immediate from the definition of C(G). If { V1, V2 } is a partition of V , the set E(V1, V2) of all the edges cut of G crossing this partition is called a cut (or cocycle). Recall that for V1 = { v } this cut is denoted by E(v). Proposition 1.9.3. Together with ∅, the cuts in G form a subspace C∗ [ 4.6.3 ] of E(G). This space is generated by cuts of the form E(v). Proof . Let C∗ denote the set of all cuts in G, together with ∅. To prove that C∗ is a subspace, we show that for all D, D ∈ C∗ also D + D (= D − D ) lies in C∗. Since D + D = ∅ ∈ C∗ and D + ∅ = D ∈ C∗, we may assume that D and D are distinct and non-empty. Let { V1, V2 } and { V 1 , V 2 } be the corresponding partitions of V . Then D + D consists of all the edges that cross one of these partitions but not the other (Fig. 1.9.1). But these are precisely the edges between (V1 ∩V 1 )∪(V2 ∩V 2 ) and (V1 ∩V 2 )∪(V2 ∩V 1 ), and by D = D these two sets form another partition of V . Hence D + D ∈ C∗, and C∗ is indeed a subspace of E(G). Our second assertion, that the cuts E(v) generate all of C∗, follows from the fact that every edge xy ∈ G lies in exactly two such cuts (in E(x) and in E(y)); thus every partition { V1, V2 } of V satisfies E(V1, V2) = v∈V1 E(v).