# proof that a cycle space is a subspace

I'm looking at the following proof that the cycle space of a graph is indeed a subspace, which I don't believe to be correct.

proof: It suffices to prove that $\mathcal{C}$ is closed under $+$ since it is trivially closed under vector-scalar multiplication. Consider two elements $C_{1}$ and $C_{2}$ $\in \mathcal{C}$.

(1) If $C_{1}$ and $C_{2}$ are the edge disjoint cycles (or the empty set) then $C_{1}$ + $C_{2}$ is simply the union of edge disjoint cycles and clearly $C_{1} + C_{2} \in \mathcal{C}$.

(2) If $C_{1}$ is a union of edge disjoint cycles and $C_{2}$ is the union of edge disjoint cycles (or the empty set) and $C_{1}$ and $C_{2}$ share no edges in common, then it is again easy to see that $C_{1} + C_{2}$ is simply the union of edge disjoint cycles and in $\mathcal{C}$.

(3) If $C_{1}$ and $C_{2}$ are unions of edge disjoint cycles but share edges in common, then $C_{1}$ and $C_{2}$ must share two or more cycles in common. In constructing $C_{1} + C_{2}$ these common cycles will be removed (through symmetric differencing).

Thus, $\mathcal{C}$ is closed under $+$ and it must be a vector space.

Why if $C_{1}$ and $C_{2}$ are both unions of edge disjoint cycles which have edges in common must they share a cycle in common?

A simple example if both are each a cycle with an edge in common so suppose

$C_{1}=x_{1}x_{2}x_{3}x_{4}x_{1}$ and $C_{2}=x_{1}x_{2}y_{3}y_{4}x_{1}$ then these do not have any cycles in common. Rather through symmetric differencing the edge $x_{1}x_{2}$ Is removed and we have a larger cycle namely $C_{1}+C_{2}=x_{1}y_{1}y_{2}y_{3}x_{2}x_{3}x_{4}x_{1}$. Is this proof correct and I'm missing something? If not does anybody know the correct way to formalize part (3)? I think it would require a proof that if we remove a common edge of two non-edge disjoint cycles then the result is still an edge disjoint cycle.

• A subspace space of what? As far as I got your $+$ operation on a pair of cycles is correct (and also described at Cycle Space:CycleBasis). Something I stumble upon from time to time is that cylces may also just be concatenated, like the following: $C_1 + C_2= x_{1}x_{2}x_{3}x_{4}x_{1}x_{2}y_{3}y_{4}x_{1}$, where I left out one $x_1$. This kind of addition was just in the connection with the Ihara $\zeta$ function, I think... – draks ... Jun 23 '15 at 10:23

Let's write down the adjacency matrices for $C_1$ and $C_2$. Now add them over the two-element finite field (take every matrix entry $\bmod 2$). This removes common edges and creates the resulting cylce.
It also shows that $C_1+C_1 \bmod 2 = E$, where $E$ is the zero matrix which is the identity element of the (abelian) group of cycles...
• How can we prove that after removing common edges the result of the addition $\mathrm{mod}\;2$ is still a cycle? – Pavan Sangha Jun 29 '15 at 19:59
• @PavanSangha I thought it might be possible to easily show that $2$ is an eigenvalue of all possible symmetric differences of cycles i.e. faces of a graph. I got stuck, but I posted a question concerning this problem, here... – draks ... Jul 22 '15 at 22:24