251.9 Some linear algebraDVDFig. 1.9.1. Cut edges in D+DThe subspace C* =: C*(G) of (G) from Proposition 1.9.3 is the cutcut spspace of G. It is not difficult to find among the cuts E(u) an explicitc*(G)basis for C*(G), and thus to determine its dimension (Exercise 27).empty cut in G is a bond. Thus, bonds are for C*Aminimal ndbondwhat cycles are for C: the minimal non-empty elements. Note that the'non-empty' condition bites only if G is disconnected. If G is connected.its bonds are just its minimal cuts, and these are easy to recognize:clearly, a cut in a connected graph is minimal if and only if both sidesof the corresponding vertex partition induce connected subgraphs. If Gis disconnected, its bonds are the minimal cuts of its components. (Seealso Lemma 3.1.1.)In analogy to Proposition 1.9.2, bonds and disjoint unions sufice togenerate C*:Lemma 1.9.4. Every cut is a disjoint union of bonds.[4.6.2]Proof. Consider first a connected graph H = (V,E), a connnectedsubgraph C C H, and a component D of H -C. Then H - D, too, isconnected (Fig. 1.9.2), so the edges between D and H - D form a mini-mal cut. By the choice of D, this cut is precisely the set E(C, D) of allC-D edges in H.H-DFig. 1.9.2. H-D is connected, and E(C,D) a minimal cut
1.9 Some linear algebra 25 V1 V2 V 1 V 2 D D Fig. 1.9.1. Cut edges in D + D The subspace C∗ =: C∗(G) of E(G) from Proposition 1.9.3 is the cut space of G. It is not difficult to find among the cuts E(v) an explicit cut space C∗(G) basis for C∗(G), and thus to determine its dimension (Exercise 27). A minimal non-empty cut in G is a bond. Thus, bonds are for C∗ bond what cycles are for C: the minimal non-empty elements. Note that the ‘non-empty’ condition bites only if G is disconnected. If G is connected, its bonds are just its minimal cuts, and these are easy to recognize: clearly, a cut in a connected graph is minimal if and only if both sides of the corresponding vertex partition induce connected subgraphs. If G is disconnected, its bonds are the minimal cuts of its components. (See also Lemma 3.1.1.) In analogy to Proposition 1.9.2, bonds and disjoint unions suffice to generate C∗: Lemma 1.9.4. Every cut is a disjoint union of bonds. [ 4.6.2 ] Proof . Consider first a connected graph H = (V,E), a connected subgraph C ⊆ H, and a component D of H − C. Then H − D, too, is connected (Fig. 1.9.2), so the edges between D and H − D form a minimal cut. By the choice of D, this cut is precisely the set E(C, D) of all C–D edges in H. D C H− D Fig. 1.9.2. H − D is connected, and E(C, D) a minimal cut
261.The BasicsTo prove the lemma, let a cut in an arbitrary graph G = (V,E)be given, with partition [Vi, V2] of V say.Consider a componentC of G[Vi], and let H be the component of G containing C. ThenE(C,V) - E(C. H - C) is the disjoint union of the edge sets E(C, D)over all the components D of H -C. By our earlier considerations thesesets are minimal cuts in H, and hence bonds in G. Now the disjointunion of all these edge sets E(C,V2), taken over all the components Cof G[V], is precisely our cut E(Vi, V2).口Theorem 1.9.5. The cycle space C and the cut space C* of any graphsatisfyC =C*1and c*=c+Proof.(See also Exercise 30.) Let us consider a graph G = (V,E).Clearly, any cycle in G has an even number of edges in each cut. Thisimplies CC*+Conversely, recall from Proposition 1.9.2 that for every edge setF C there exists a vertex v incident with an odd number of edges in F.Then (E(u), F) = 1, so E(u) e C* implies F C*+, This completes theproof of C = C*1To prove c* = C+, it now sufices to show C* = (C*+). HereC* (c*)+ follows directly from the definition of I. But C* has thesame dimension as (c++)-, since (t) impliesdimc*+ dimc*+ = m = dimc*++ dim (c*+).口Hence C* = (c*+)+ as claimed.Consider a connected graph G = (V, E) with a spanning tree T C GRecall that for every edge e e E E(T) there is a unique cycle Cefundamental in T+e (Fig. 1.6.3); these cycles Ce are the fundamental cycles of G withcyclesrespect to T. On the other hand, given an edge e e T, the graph T-e(1.5.1)has exactly two components (Theorem 1.5.1(ii), and the set D. Eof edges between these two components form a bond in G (Fig.1.9.3)fundamentalThese bonds D are the fundamental cuts of G with respect to TcutsIt is not difficult to show directly that the fundamental cycles andcuts span the cycle and cut space of G, respectively (Ex. 31-32). In theproof of the following more compreheensive theoorem,this informationcomes for free as a consequence of Theorem 1.9.5 and the dimensionformula (t) for orthogonal subspaces[4.5.1]Theorem 1.9.6. Let G be a connected graph and T C G a spanningtree. Then the corresponding fundamental cycles and cuts form a basisof C(G) and of C*(G), respectively. If G has n vertices and m edges,thendimc(G) = m-n+1 and dimc*(G) = n-1
26 1. The Basics To prove the lemma, let a cut in an arbitrary graph G = (V,E) be given, with partition { V1, V2 } of V say. Consider a component C of G [ V1 ], and let H be the component of G containing C. Then E(C, V2) = E(C, H − C) is the disjoint union of the edge sets E(C, D) over all the components D of H −C. By our earlier considerations these sets are minimal cuts in H, and hence bonds in G. Now the disjoint union of all these edge sets E(C, V2), taken over all the components C of G [ V1 ], is precisely our cut E(V1, V2). Theorem 1.9.5. The cycle space C and the cut space C∗ of any graph satisfy C = C∗⊥ and C∗ = C⊥ . Proof . (See also Exercise 30.) Let us consider a graph G = (V,E). Clearly, any cycle in G has an even number of edges in each cut. This implies C⊆C∗⊥. Conversely, recall from Proposition 1.9.2 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) ∈ C∗ implies F /∈ C∗⊥. This completes the proof of C = C∗⊥. To prove C∗ = C⊥, it now suffices to show C∗ = (C∗⊥)⊥. Here C∗ ⊆ (C∗⊥)⊥ follows directly from the definition of ⊥. But C∗ has the same dimension as (C∗⊥)⊥, since (†) implies dim C∗ + dim C∗⊥ = m = dim C∗⊥ + dim (C∗⊥) ⊥. Hence C∗ = (C∗⊥)⊥ as claimed. Consider a connected graph G = (V,E) with a spanning tree T ⊆ G. Recall that for every edge e ∈ E E(T) there is a unique cycle Ce in T +e (Fig. 1.6.3); these cycles Ce are the fundamental cycles of G with fundamental cycles respect to T. On the other hand, given an edge e ∈ T, the graph T − e (1.5.1) has exactly two components (Theorem 1.5.1 (iii)), and the set De ⊆ E of edges between these two components form a bond in G (Fig.1.9.3). These bonds De are the fundamental cuts of G with respect to T. fundamental cuts It is not difficult to show directly that the fundamental cycles and cuts span the cycle and cut space of G, respectively (Ex. 31–32). In the proof of the following more comprehensive theorem, this information comes for free as a consequence of Theorem 1.9.5 and the dimension formula (†) for orthogonal subspaces. [ 4.5.1 ] Theorem 1.9.6. Let G be a connected graph and T ⊆ G a spanning tree. Then the corresponding fundamental cycles and cuts form a basis of C(G) and of C∗(G), respectively. If G has n vertices and m edges, then dim C(G) = m − n + 1 and dim C∗(G) = n − 1
271.9 Some linear algebraFig. 1.9.3. The fundamental cut DProof. Since an edge e e T lies in D, but not in D for any e' + e, the cut(1.5.3)De cannot be generated by other fundamental cuts. The fundamentalcuts therefore form a linearly independent subset of c*, of size n-1(Corollary 1.5.3). Similarly, an edge e e EE(T) lies on Cebut not onany other fundamental cycle; so the fundamental cycles form a linearlyindependent subset of C, of size m - n + 1. Thus,dimc*≥n-1 and dimc>m-n+1.ButdimC*+dimC=m=(n-1)+(m-n+1)by Theorem 1.9.5 and (f), so the two inequalities above can hold onlywith equality.Hence the sets of fundamental cuts and cycles are maximalas linearly independent subsets of c* and C, and hence are bases.incideThe incidence matrir B = (bjs)nxm of a graph G = (V,E) withmatrixV- ( u,..., n } and E -- fei,..,em ] is defined over F, by[1ifuieejby :- o otherwise.As usual, let Bt denote the transpose of B. Then B and Bt define linearmaps B: 8(G)- V(G) and Bt: V(G)-(G) with respect to the standardbases.Proposition 1.9.7.(i) The kernel of B is C(G)口(i) The image of Bt is C*(G)
1.9 Some linear algebra 27 e Fig. 1.9.3. The fundamental cut De Proof . Since an edge e ∈ T lies in De but not in De for any e = e, the cut (1.5.3) De cannot be generated by other fundamental cuts. The fundamental cuts therefore form a linearly independent subset of C∗, of size n − 1 (Corollary 1.5.3). Similarly, an edge e ∈ E E(T) lies on Ce but not on any other fundamental cycle; so the fundamental cycles form a linearly independent subset of C, of size m − n + 1. Thus, dim C∗ n − 1 and dim C m − n + 1 . But dim C∗ + dim C = m = (n − 1) + (m − n + 1) by Theorem 1.9.5 and (†), so the two inequalities above can hold only with equality. Hence the sets of fundamental cuts and cycles are maximal as linearly independent subsets of C∗ and C, and hence are bases. 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. Proposition 1.9.7. (i) The kernel of B is C(G). (ii) The image of Bt is C∗(G).
281.The BasicsadjacencyThe adjacency matrir A = (ais)nxn of G is defined bymatrix[lifuujeEa i=10otherwiseOur last proposition establishes a simple connection between A and B(now viewed as real matrices). Let D denote the real diagonal matrix(d.g)nxn with di = d(u:) and dj, = O otherwise.口Proposition 1.9.8. BBt = A+ D.1.10 Other notions of graphsFor 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 elementshypergraphof E are non-empty subsets (of any cardinality) of V.Thus, graphs arespecial hypergraphsdirectedA directed graph (or digraph) is a pair (V,E) of disjoint sets (ofgraphvertices and edges) together with two maps init:EVand ter:E-Vinit(e)assigning to every edge e an initial verter init(e) and a terminal verteater(e). The edge e is said to be directed from init(e) to ter(e). Note thatter(e)adirected graphmay have several edgesbetweenthe sametwo vertice, y. Such edges are called multiple edges; if they have the same direction(say from r to y), they are parallel. If init(e) = ter(e),the edge e is calledloopaloop.orientationA directed graph D is an orientation of an (undirected) graph G ifV(D) = V(G) and E(D) = E(G), and if [init(e),ter(e)) = (r,y) foroterevery edge ery. Intuitively, such an oriented graph arises from angraphundirected graph simply by directing every edge from one of its ends tothe other. Put differently, oriented graphs are directed graphs withoutloops or multiple edgesA multigraph is a pair (V,E) of disjoint sets (of vertices and edges)multigraphtogether with a map E - Vu[V]? assigning to every edge either oneor two vertices, its ends. Thus, multigraphs too can have loops andmultiple edges: we may think of a multigraph as a directed graph whoseedge directions have been "forgotten. To express that r and y are theends of an edge e we still write e = ry, though this no longer determinese uniquelyA graph is thus essentially the same as a multigraph without loopsor multiple edges. Somewhat surprisingly,proving a graph theorem moregenerally for multigraphs may, on occasion, simplify the proof. Moreover.there are areas in graph theory (such as plane duality; see Chapters 4.6and 6.5) where multigraphs arise more naturally than graphs, and where
28 1. The Basics The adjacency matrix A = (aij )n×n of G is defined by adjacency matrix aij := 1 if vivj ∈ E 0 otherwise. Our last proposition establishes a simple connection between A and B (now viewed as real matrices). Let D denote the real diagonal matrix (dij )n×n with dii = d(vi) and dij = 0 otherwise. Proposition 1.9.8. BBt = A + D. 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. hypergraph A hypergraph is a pair (V,E) of disjoint sets, where the elements 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 init(e) assigning to every edge e an initial vertex init(e) and a terminal vertex ter(e) ter(e). The edge e is said to be directed from init(e) to ter(e). Note that a directed graph may have several edges between the same two vertices x, y. Such edges are called multiple edges; if they have the same direction (say from x to y), they are parallel. If init(e) = ter(e), the edge e is called loop a loop. orientation A directed graph D is an orientation of an (undirected) graph G if V (D) = V (G) and E(D) = E(G), and if { init(e),ter(e) } = { x, y } for every edge e = xy. Intuitively, such an oriented graph arises from an oriented graph undirected graph simply by directing every edge from one of its ends to the other. Put differently, oriented graphs are directed graphs without loops or multiple edges. multigraph A multigraph is a pair (V,E) of disjoint sets (of vertices and edges) together with a map E → V ∪ [V ] 2 assigning to every edge either one or two vertices, its ends. Thus, multigraphs too can have loops and multiple edges: we may think of a multigraph as a directed graph whose edge directions have been ‘forgotten’. To express that x and y are the ends of an edge e we still write e = xy, though this no longer determines e uniquely. A graph is thus essentially the same as a multigraph without loops or multiple edges. Somewhat surprisingly, proving a graph theorem more generally for multigraphs may, on occasion, simplify the proof. Moreover, there are areas in graph theory (such as plane duality; see Chapters 4.6 and 6.5) where multigraphs arise more naturally than graphs, and where
291.10 Other notions of graphsany restriction to the latter would seem artificial and be technicallycomplicated.Weshall therefore consider multigraphs in thesecases.butwithout much technical ado: terminology introduced earlier for graphswill be used correspondingly.A few differences, however, should be pointed out.Amultigraphmay have cycles of length 1 or 2: loops, and pairs of multiple edges(or double edges). A loop at a vertex makes it its own neighbour, andcontributes 2 to its degree; in Figure 1.10.1, we thus have d(ve) = 6.And the notion of edge contraction is simpler in multigraphs than ingraphs.Ifwecontract an edge e:ry in a multigraph G = (V,E) to anew vertex ve, there is no longer a need to delete any edges other thane itself: edges paralel to e become loops at ve, while edges zu and yubecome parallel edges between ve and u (Fig. 1.10.1). Thus, formallyE(G/e) = E-(e}, and only the incidence map e' - [init(e'),ter(e))of G has to be adjusted to the new vertex set in G/e. The notion of aminor adapts to multigraphs accordingly.GeFig. 1.10.1. Contracting the edge e in the multigraph corre-sponding to Fig. 1.8.1suppressingIf v is a vertex of degree 2 in a multigraph G, then by suppressing uavertexwe mean deleting and adding an edge between its two neighbours.11(If its two incident edges are identical, i.e. form a loop at v, we add noedge and obtain just G - . If they go to the same vertex w + u, theadded edge will be a loop at w. See Figure 1.10.2.) Since the degreesof all vertices other than w remain unchanged when u is suppressed,suppressing several vertices of G always yields a well-defined multigraphthat is independent of the order in which those vertices are suppressed.-0Fig. 1.10.2. Suppressing the white vertices11This is just a clumsy combinatorial paraphrase of the topological notion ofamalgamating the two edges at u into one edge, of which becomes an inner point
1.10 Other notions of graphs 29 any restriction to the latter would seem artificial and be technically complicated. We shall therefore consider multigraphs in these cases, but without much technical ado: terminology introduced earlier for graphs will be used correspondingly. A few differences, however, should be pointed out. A multigraph may have cycles of length 1 or 2: loops, and pairs of multiple edges (or double edges). A loop at a vertex makes it its own neighbour, and contributes 2 to its degree; in Figure 1.10.1, we thus have d(ve) = 6. And the notion of edge contraction is simpler in multigraphs than in graphs. If we contract an edge e = xy in a multigraph G = (V,E) to a new vertex ve, there is no longer a need to delete any edges other than e itself: edges parallel to e become loops at ve, while edges xv and yv become parallel edges between ve and v (Fig. 1.10.1). Thus, formally, E(G/e) = E { e }, and only the incidence map e → { init(e ),ter(e ) } of G has to be adjusted to the new vertex set in G/e. The notion of a minor adapts to multigraphs accordingly. G G/e e ve Fig. 1.10.1. Contracting the edge e in the multigraph corresponding to Fig. 1.8.1 If v is a vertex of degree 2 in a multigraph G, then by suppressing v suppressing a vertex we mean deleting v and adding an edge between its two neighbours.11 (If its two incident edges are identical, i.e. form a loop at v, we add no edge and obtain just G − v. If they go to the same vertex w = v, the added edge will be a loop at w. See Figure 1.10.2.) Since the degrees of all vertices other than v remain unchanged when v is suppressed, suppressing several vertices of G always yields a well-defined multigraph that is independent of the order in which those vertices are suppressed. Fig. 1.10.2. Suppressing the white vertices 11 This is just a clumsy combinatorial paraphrase of the topological notion of amalgamating the two edges at v into one edge, of which v becomes an inner point.