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 cut1.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 sub￾graph 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 mini￾mal 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