Writing cycles of a graph as a linear combination of fundamental cycles

Question

It is folklore that the fundamental cycles (corresponding to aparticular spanning tree) of a graph constitute a basis for its cycle space, while the proof uses the linear indepence of fundamental cycles as well as some orthogonality arguements (see chapter 1 of Diestel’s Text book for more context).

But I could not find any constructive way for writing an arbitrary cycle as a linear combination of fundamental cycles in the litrature, and my personal effort also did not get to anywhere.

Is there any such way of writing the precise linear combination, preferably a purely combinatorial one?

All answers and comments are appreciated.

Answer 1

Knowing the spanning tree $T$ that gives us the fundamental cycles $\{C_e : e \notin T\}$, there is a simple algorithm: given an arbitrary cycle $C$, we can write $C$ as the sum $$ C = \sum_{e \in C \setminus T} C_e. $$ That is, we take all the fundamental cycles corresponding to edges of $C$ which are not edges of the tree $T$.

This works because:

• If $e \in C \setminus T$, then we must include the fundamental cycle $C_e$, because it is the only fundamental cycle containing the edge $e$, and we must get that edge from somewhere.
• If $e \notin C \cup T$, then we cannot include the fundamental cycle $C_e$, because it contains the edge $e$, which does not belong in $C$ and cannot be cancelled out by any other fundamental cycle.

So the sum given above is the only one which could possibly work. On the other hand, we have some sort of proof that the fundamental cycles form a basis, or at least Diestel does. So there is some sum that does work, and therefore it is this one.