231.8 Euler tourProoThoclearlv1times in an Euler tour (or k+1 times.if it is the starting and finishingvertex and as such counted twice) must have degree 2k.Conversely, we show by induction on Gll that every connectedgraph G with all degrees even has an Euler tourThe induction startstrivially with IGl - 0. Now let IG ≥ 1. Since all degrees are even,we can find in G a non-trivial closed walk that contains no edge morethan once.(Howexactly?)Let Wbesuch awalk ofmaximal lengthandwriteFfofor theset ofedees. If F - E(G).then W is an Eulertour. Suppose, therefore, that G' :- G- F has an edge.For every vertex y e G, an even number of the edges of G at u liesin F so the degrees of G' are again all even. Since G is connected. G' hasan edge e incident with a vertex on W. By the induction hypothesisthe component C of G' containing e has an Euler tour. Concatenatingthis with W (suitably re-indexed), we obtain a closed walk in G thatcontradicts the maximal length of W国1.9 Some linear algebra[8.7]Let G = (V,E) be a graph with n vertices and m edges, say VG= (V,E)J.The verter space V(G) of G is thefu1....nl and E -fei.....emvectorspaceoverthe2-element fieldF= (o,1] ofallfunctionsF2spaceV(G)Every element of V(G) corresponds naturally to a subset of V, the set ofthoseverticesh it assigns a 1, and every subset of V is uniquelyrepresented in v(G) by its indicator function. We may thus think ofset of V made into a vector space: the sum U +UV(G) as the power se+of two vertex sets U,U' V is their symmetric difference (why?), and--U forall U CV.Thezero in V(G),viewed in this way.isthe empty (vertex) set 0. Since (fui).... un)) is a basis of v(G), itsstandardbasis,wehavedimV(G)=way as above, the functions E-F2 form the edge spacentheedge "P(C)E(G) of G: its elemets correspond to the subsets of E, vector additionounts to symmetric difference,Eis the zero, and F=-Ffor alstandardF C E. As before, (feil....fem)) is the standard basis of e(G), anddim&(G) = m. Given two elements F, F' of the edge space, viewed asfunctions E-F2.wewrite(F, F') := E F(e)F'(e) e F2 .(F,F")This is zero if and only if F and F' have an even number of edges incommon; in particular, we can have (F, F) =- 0 with F + 0. Given a
1.8 Euler tours 23 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. Conversely, we show by induction on G that every connected graph G with all degrees even has an Euler tour. The induction starts trivially with G = 0. Now let G 1. Since all degrees are even, we can find in G a non-trivial closed walk that contains no edge more than once. (How exactly?) Let W be such a walk of maximal length, and write F for the set of its edges. If F = E(G), then W is an Euler tour. Suppose, therefore, that G := G − F has an edge. For every vertex v ∈ G, an even number of the edges of G at v lies in F, so the degrees of G are again all even. Since G is connected, G has an edge e incident with a vertex on W. By the induction hypothesis, the component C of G containing e has an Euler tour. Concatenating this with W (suitably re-indexed), we obtain a closed walk in G that contradicts the maximal length of W. 1.9 Some linear algebra Let G = (V,E) be a graph with n vertices and m edges, say V = [8.7] 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 correspond to 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), and standard basis dim E(G) = m. Given two elements F, F of the edge space, viewed as functions E →F2, we write F, F := e∈E F(e)F (e) ∈ F2 . F, F This is zero if and only if F and F have an even number of edges in common; in particular, we can have F, F = 0 with F = ∅. Given a
241. The Basicssubspace F of E(G), we writeFlF+ := [D e (G) I (F,D) = 0 for all F e F)Thisisagainasubspaceof(G)(thespace ofall vectors solving acertainset of linear equations-which?), and one can show thatdim F+ dim F = m.cycle spaceThe cycle space C = C(G) is the subspace of (G) spanned by allC(G)the cvcles in Gloreprecisely,bytheir edgeo ThedimensionofC(G) is sometimes called the cyclomatic number of G.The elements of C are easily recognized by the degrees of the subgraphs they form. Moreover, to generate the cycle space from cycles weonly need disjoint unions rather than arbitrary svmmetric differences:[13.2Proosition 1.9.1. The following assertionss are equivalent for edge setsDCE(i) D eC(G):(i) D is a (possibly empty) disjoint union of edge sets of cycles in G(ii) All vertex degrees of the graph (V, D) are even.Proof. Since cycles have even degrees and taking symmetric differencespreserves this, (i)-(ii) follows by induction on the number of cycles usedto generate D. The implication (ii)-(i) follows by induction on |D):if D + 0 then (V,D) contains a cycle C, whose edges we delete for theinduICion step. The implication (i)-(i) is immediate from the definitionof c(G).口A set Fofedges isa cut in Gifthereexists apartition [Vi,]cutofvsthat F = E(Vi, V2). The edges in F are said to crosssthiuchfpartition. The sets V,V, are the sides of the cut. Recall that forVi = (u) this cut is denoted by E(u). A minimal non-empty cut in G isbondabond[4.6.3]Proposition 1.9.2. Together with 0, the cuts in G form a subspaceB - B(G) of (G). This space is generated by cuts of the form E(u).Proof. Let B denote the subspace of e(G) generated by the cuts of theform E(o), Every cut of G, with vertex partition (Vi.) say, equalswey, E(u) and hence lies in B. Conversely, every set E(u)eBis either empty, e.g. if U e [0, V], or it is the cut E(U, VU).0 For simplicity, we shall not always distinguish betweehe edge sets F e E(G)nse,suclasinChaper8.6,weshallusethewordcircuitortheedgesetfacye11 Recall that partition classes in this book arenon-empty.The empty set of edgestherefore, is a cut only if the graph is disconnected
24 1. The Basics 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 one can show that 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. 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: Proposition 1.9.1. The following assertions are equivalent for edge sets [4.5.1] [8.7.3] D ⊆ E: (i) D ∈ C(G); (ii) D is a (possibly empty) disjoint union of edge sets of cycles in G; (iii) All vertex degrees of the graph (V,D) 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 D. The implication (iii)→(ii) follows by induction on |D|: if D = ∅ then (V,D) contains a cycle C, whose edges we delete for the induction step. The implication (ii)→(i) is immediate from the definition of C(G). A set F of edges is a cut in G if there exists a partition11 cut {V1, V2} of V such that F = E(V1, V2). The edges in F are said to cross this partition. The sets V1, V2 are the sides of the cut. Recall that for V1 = {v} this cut is denoted by E(v). A minimal non-empty cut in G is bond a bond. [4.6.3] Proposition 1.9.2. Together with ∅, the cuts in G form a subspace B = B(G) of E(G). This space is generated by cuts of the form E(v). Proof. Let B denote the subspace of E(G) generated by the cuts of the form E(v). Every cut of G, with vertex partition {V1, V2} say, equals v∈V1 E(v) and hence lies in B. Conversely, every set u∈U E(u) ∈ B is either empty, e.g. if U ∈ {∅, V }, or it is the cut E(U, V U). 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.6, we shall use the word ‘circuit’ for the edge set of a cycle. 11 Recall that partition classes in this book are non-empty. The empty set of edges, therefore, is a cut only if the graph is disconnected.
251.9SomelinealgebrPror1.9.2 is the cut space,or bonion000cout B(CO)ofG.Itisnot dificulttofind among thecutsE(o)anexplicitbasisfor B, and thus to determine its dimension (Exercise 40). Note that thebonds are for B what cycles are for C: the minimal non-empty elements.The 'non-empty' condition in the definition of a bond bites only ifG is disconnected. If G is connected, its bonds are just its minimal cuts,and these are easy to recognize: a cut in a connected graph is minimalif and only if both sides of thecoondingvertexpartitioninduceonnected subgraphs (Exercise 36).If G is disconnected, its bonds arethe minmalcuts of its componeIn analogytoProosition9,bonds anddisjoint unions suficeogenerate the cut space:16.83Lemma1.9.3.Everycut isadisiointunion of bondsProof. We apply induction on the size of the cut F considered.For7=0thetion is trivial (with the empty union). If F + 0 is notitselfabond, it properly contains some other non-empty cutF'ByProposition 1.9.2, also FF'F + F' is a smaller non-empty cut.Bythe induction hypothesis,both F'andFF'are disjoint unions ofbonds, and hence so is F口Exercise 39 indicates how to construct the bonds for Lemma 1.9.3explicitly, In Chapter 3.1 we shall prove some more details about thepossible positions of the cycles and bonds of a graph within its overallstructure (Lemmas 3.1.2 and 3.1.3)Theorem 1.9.4. The cycle space C and the cut space B of any graph[4.6]satisfyand B=c+C = B+(a)Proof.Consider a graph G = (V,E). Clearly, any cycle in G has aneven number of edges in each cut. This implies C C BBIandBcClToproveBCC,recallfromProposition1.9.1thatforeveryedgeset F C there exists a vertex u incident with an odd number of edgesin F. Then (E(u), F) = 1, so E(u) B implies F B+. This completesthe proof of cTo prove C+ C B, let F e C be given. Consider the multigraph12 Hobtained from G by contracting the edges in EF.Any cycle in H hasall its edges in F. Since we can extend it to a cycle in G by edgesfrom E F, the number of these edges must be even. Hence H is bipar-tite, by Proposition 1.6.1.Its bipartition induces a bipartition (V)of V such that E(Vi, V2) = F, showing F e B as desired国See Section 1.i0: such contractions might createps in F, but bipartite multi-graphshavenoloops.TheproofofPropostion1.6.1works formultigraphs tc
1.9 Some linear algebra 25 The space B from Proposition 1.9.2 is the cut space, or bond space, of G. It is not difficult to find among the cuts E(v) an explicit basis cut space B(G) for B, and thus to determine its dimension (Exercise 40). Note that the bonds are for B what cycles are for C: the minimal non-empty elements. The ‘non-empty’ condition in the definition of a bond bites only if G is disconnected. If G is connected, its bonds are just its minimal cuts, and these are easy to recognize: a cut in a connected graph is minimal if and only if both sides of the corresponding vertex partition induce connected subgraphs (Exercise 36). If G is disconnected, its bonds are the minimal cuts of its components. In analogy to Proposition 1.9.1, bonds and disjoint unions suffice to generate the cut space: Lemma 1.9.3. Every cut is a disjoint union of bonds. [4.6.2] [6.5.2] Proof. We apply induction on the size of the cut F considered. For F = ∅ the assertion is trivial (with the empty union). If F = ∅ is not itself a bond, it properly contains some other non-empty cut F . By Proposition 1.9.2, also F F = F + F is a smaller non-empty cut. By the induction hypothesis, both F and F F are disjoint unions of bonds, and hence so is F. Exercise 39 indicates how to construct the bonds for Lemma 1.9.3 explicitly. In Chapter 3.1 we shall prove some more details about the possible positions of the cycles and bonds of a graph within its overall structure (Lemmas 3.1.2 and 3.1.3). Theorem 1.9.4. The cycle space C and the cut space B of any graph [4.6] satisfy C = B⊥ and B = C⊥ . Proof. Consider a graph G = (V,E). Clearly, any cycle in G has an (1.6.1) (1.10) even number of edges in each cut. This implies C⊆B⊥ and B⊆C⊥. To prove B⊥ ⊆ C, recall from Proposition 1.9.1 that for every edge set F /∈ C there exists a vertex v incident with an odd number of edges in F. Then E(v), F = 1, so E(v) ∈ B implies F /∈ B⊥. This completes the proof of C = B⊥. To prove C⊥ ⊆ B, let F ∈ C⊥ be given. Consider the multigraph12 H obtained from G by contracting the edges in E F. Any cycle in H has all its edges in F. Since we can extend it to a cycle in G by edges from E F, the number of these edges must be even. Hence H is bipartite, by Proposition 1.6.1. Its bipartition induces a bipartition (V1, V2) of V such that E(V1, V2) = F, showing F ∈ B as desired. 12 See Section 1.10: such contractions might create loops in F, but bipartite multigraphs have no loops. The proof of Proposition 1.6.1 works for multigraphs too.
261. The BasicsConsider a connected graph G= (V,E) with a spanning tree T CGFor every chord e e EE(T)there is a unique cycle Ce in T+e,thefundamentalfundamental cycle of e withrespect toT.Similarly,for every edge f eTcycle/cutthe forest T-f has exactly two components (Theorem 1.5.1(i)). The(1.5.1)set D E of edges of G between these components is a bond in G, thefundamental cut of f with respect to T.Notice that f e Ce if and only if e eDf, for all edges e T andf eT. This is an indication of some deeper duality, which the followingtheorem exploresfurther.Fig.1.9.1.The fundamental cycle Ce, and the fundamental cut D,Theorem1.9.5.Let Gbea connected graph withn vertices and[4.5.1]m edges, and let T G a spanning tree.(i) Thefundamental cuts and cycles of G with respect to T formbases of B(G) and C(G),respectively.(i) Hence, dimB(G) = n-1 and dimC(G) =m-n+1.Proof. (i)Note that an edge f eT lies in D,but in no other fundamental(1.5.3)cut, while an edge e T lies in Ce but in no other fundamental cycleHence the fundamental cuts and cycles form linearly independent setsin B = B(G) and C = C(G), respectively.Let us show that the fundamental cycles generate every cycle C.Byour initial observation, D := C+ Eeec- Ce is an element of C thatcontains no edge outside T. But by Proposition 1.9.1, the only elementof C contained in T is 0. So D = O, giving C = ZeeC-T Ce.Similarly, every cut D is a sum of fundamental cuts. Indeed, theelement D+ZfeDnr Dy of B contains no edge of T. As 0 is the onlyelement of B missing T, this implies D = feDnr Df.(i) By (i), the fundamental cuts and cycles form bases of B and CAs there are n-1 fundamental cuts (Corollary1.5.3),there are m-n +1口fundamental cycles
26 1. The Basics Consider a connected graph G = (V,E) with a spanning tree T ⊆ G. For every chord e ∈ E E(T) there is a unique cycle Ce in T + e, the fundamental cycle of e with respect to T. Similarly, for every edge f ∈ T fundamental cycle/cut the forest T − f has exactly two components (Theorem 1.5.1 (iii)). The (1.5.1) set Df ⊆ E of edges of G between these components is a bond in G, the fundamental cut of f with respect to T. Notice that f ∈ Ce if and only if e ∈ Df , for all edges e /∈ T and f ∈ T. This is an indication of some deeper duality, which the following theorem explores further. f e Ce Df T T Fig. 1.9.1. The fundamental cycle Ce, and the fundamental cut Df [4.5.1] Theorem 1.9.5. Let G be a connected graph with n vertices and m edges, and let T ⊆ G a spanning tree. (i) The fundamental cuts and cycles of G with respect to T form bases of B(G) and C(G), respectively. (ii) Hence, dim B(G) = n − 1 and dim C(G) = m − n + 1. (1.5.3) Proof. (i) Note that an edge f ∈ T lies in Df but in no other fundamental cut, while an edge e /∈ T lies in Ce but in no other fundamental cycle. Hence the fundamental cuts and cycles form linearly independent sets in B = B(G) and C = C(G), respectively. Let us show that the fundamental cycles generate every cycle C. By our initial observation, D := C + e∈CT Ce is an element of C that contains no edge outside T. But by Proposition 1.9.1, the only element of C contained in T is ∅. So D = ∅, giving C = e∈CT Ce. Similarly, every cut D is a sum of fundamental cuts. Indeed, the element D + f ∈D∩T Df of B contains no edge of T. As ∅ is the only element of B missing T, this implies D = f ∈D∩T Df . (ii) By (i), the fundamental cuts and cycles form bases of B and C. As there are n−1 fundamental cuts (Corollary 1.5.3), there are m−n+ 1 fundamental cycles.
271.9 Some linear algebraincidenceThe incidence matrir B = (bi)nxm of a graph G = (V,E) withmatrixV = [ui,..., Un] and E = [ei,..., em) is defined over F2 byifueejbij :-10otherwise.As usual, let Bt denote the transpose of B. Then B and Bt definelinearmapsB:(G)-→V(G)and Bt:V(G)-E(G)with respecttothestandard bases. As is easy to check, B maps an edge set F E to theset of vertices incident with an odd number of edges in F, while Bt mapsa set U C V to set of edges with exactly one end in U. In particular:Proposition1.9.6.(i) Thekernel of B is C(G),口(ii) The image of Bt is B(G).More on this in the exercises and notes at the end of this chapter.adjacencyThe adjacency matrir A= (aig)nxn of G is defined bymatrix[lifuujEaij:lootherwise.Viewed as a linear mapV→V,the adjacencymatrix maps agiven setU CVto the set of verticeswith an odd number of neighbours in ULet D denote the real diagonal matrix (di)nxn with di = d(vi)and dij = 0 otherwise. Our last proposition establishes a connectiorbetween A and B (now viewed as real matrices),which can be verifiedsimply from the definition of matrix multiplication:口Proposition1.9.7.BBt=A+D.It is also instructive to check that A + D, with entries taken mod 2,defines the same map V- V as the composition of the maps of B and Bt(Exercise 48).1.10OthernotionsofgraphsFor completeness, we now mention a few other notions of graphs whichfeature less frequently or not at all in this book.A hypergraph is a pair (V,E) of disjoint sets, where the elements hypergraphof E are non-empty subsets (of any cardinality) of V. Thus, graphs arespecial hypergraphs.directedA directed graph (or digraph) is a pair (V,E) of disjoint sets (ofgraphuertices and edges)togetherwith two maps init:E-V and ter:E-→V
1.9 Some linear algebra 27 The incidence matrix B = (bij )n×m of a graph G = (V,E) with incidence matrix V = {v1,...,vn} and E = {e1,...,em} is defined over F2 by bij := 1 if vi ∈ ej 0 otherwise. As usual, let Bt denote the transpose of B. Then B and Bt define linear maps B: E(G) → V(G) and Bt : V(G) → E(G) with respect to the standard bases. As is easy to check, B maps an edge set F ⊆ E to the set of vertices incident with an odd number of edges in F, while Bt maps a set U ⊆ V to set of edges with exactly one end in U. In particular: Proposition 1.9.6. (i) The kernel of B is C(G). (ii) The image of Bt is B(G). More on this in the exercises and notes at the end of this chapter. The adjacency matrix A = (aij )n×n of G is defined by adjacency matrix aij := 1 if vivj ∈ E 0 otherwise. Viewed as a linear map V→V, the adjacency matrix maps a given set U ⊆ V to the set of vertices with an odd number of neighbours in U. Let D denote the real diagonal matrix (dij )n×n with dii = d(vi) and dij = 0 otherwise. Our last proposition establishes a connection between A and B (now viewed as real matrices), which can be verified simply from the definition of matrix multiplication: Proposition 1.9.7. BBt = A + D. It is also instructive to check that A + D, with entries taken mod 2, defines the same map V→V as the composition of the maps of B and Bt (Exercise 48). 1.10 Other notions of graphs For completeness, we now mention a few other notions of graphs which feature less frequently or not at all in this book. A hypergraph is a pair (V,E) of disjoint sets, where the elements hypergraph of E are non-empty subsets (of any cardinality) of V . Thus, graphs are special hypergraphs. A directed graph (or digraph) is a pair (V,E) of disjoint sets (of directed graph vertices and edges) together with two maps init: E → V and ter: E → V