0
$\begingroup$

In graph theory, the cycle space of a connected, undirected finite graph consists of all Eulerian (all vertices have only even degrees) subgraphs. It's easy to see why cycles generate (using symmetric difference as 'addition') only such subgraphs, but I cannot find a proof of the opposite, namely that each Eulerian subgraph is a member of the cycle space - how easy is it to show that? Since I have not received any answer yet, let me try my own proof: any Eulerian subgraph must contain at least one cycle (start at any positive-degree vertex of the subgraph and continue 'walking' through consecutively adjacent vertices till re-vising a vertex, and thus completing a cycle; this is always possible since every new vertex you enter has at least one extra incident edge to leave, until you re-visit a vertex). Then, remove all the edges of this cycle from the original subgraph; what remains is another Eulerian subgraph (since the degree of every vertex we have visited has been reduced by two). This can be repeated till no edges remain. This shows that a Eulerian subgraph consist of a union of cycles (potentially sharing vertices but not edges); such a union is clearly a member of the cycle space.

$\endgroup$
0

1 Answer 1

1
$\begingroup$

A silly answer is that if we define the cycle space to have all Eulerian subgraphs as its elements, then each Eulerian subgraph is in the cycle space by definition. That's obviously not what you mean. You want to define the cycle space to be the vector space generated by symmetric-difference addition of all cycles. Then, the question you want can be stated purely graph-theoretically as:

Can (the edge set of) every Eulerian graph be represented as the symmetric difference of one or more cycles?

Your proof is exactly the proof I would give that the answer is yes. It actually shows a stronger claim: that every Eulerian graph has a decomposition into edge-disjoint cycles, for which symmetric difference can be replaced with plain union.

Another way to prove this claim is to prove that a fundamental cycle basis spans the cycle space (as in your previous question). The elements of a fundamental cycle basis are all cycles, and what we'd prove there is exactly that every Eulerian graph is the symmetric difference of one or more cycles in the fundamental cycle basis.

This is a bit overkill for this question, though it is a valid argument. We limit our choice of cycles to only the cycles in the cycle basis. This means we have to do more work to finish the proof, and that we are forced to use symmetric difference and not just edge-disjoint union.

$\endgroup$
1
  • $\begingroup$ Yes, in view of your answer to my previous question, the fact that any Eulerian subgraph can be expressed as a symmetric difference of cycles from a cycle-space basis then follows automatically. $\endgroup$
    – Honza
    Dec 23, 2020 at 13:16

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .