1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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... $\endgroup$ – draks ... Jun 23 '15 at 10:23
1
$\begingroup$

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...

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ How can we prove that after removing common edges the result of the addition $\mathrm{mod}\;2$ is still a cycle? $\endgroup$ – Pavan Sangha Jun 29 '15 at 19:59
  • $\begingroup$ @PavanSangha would this question/answer help you: math.stackexchange.com/q/506201/19341 ...? $\endgroup$ – draks ... Jul 21 '15 at 22:11
  • $\begingroup$ @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... $\endgroup$ – draks ... Jul 22 '15 at 22:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.