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 sub￾graphs 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).