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