TAOCP 2.3.4.1 Exercise 9
The splitting of edges $e_{13}$ and $e_{19}$ was introduced solely to satisfy the formal definition of a graph in which no two edges may join the same pair of vertices.
Exercise 9. [**] $$M22$$ Edges $e_{13}$ and $e_{19}$ were split into two parts in Fig. 32, since a graph is not supposed to have two edges joining the same two vertices. However, if we look at the final result of the construction, this splitting into two parts seems quite artificial since $E'{13}=E''{13}$ and $E'{19}=E''{19}$ are two of the relations found in (6), while $E''{13}$ and $E''{19}$ are two of the independent variables. Explain how the construction could be generalized so that an artificial splitting of edges may be avoided.
Verified: no
Solve time: 3m15s
The splitting of edges $e_{13}$ and $e_{19}$ was introduced solely to satisfy the formal definition of a graph in which no two edges may join the same pair of vertices. The construction of fundamental cycles and the independence of the edge flows do not rely on the edges being distinct in this way; they depend only on the connectivity of the free subtree. Therefore, one can generalize the construction by allowing multiple edges between the same pair of vertices, treating them as a single edge when forming the free subtree. In this generalized approach, each edge corresponds to exactly one independent variable in the cycle basis, and any relations such as $E'{13}=E''{13}$ or $E'{19}=E''{19}$ arise naturally without requiring artificial splitting. The cycles can be defined directly in terms of the original edges, with the same uniqueness and independence properties as in the standard construction.
This completes the proof.
∎