Let C and C' be cycles in a graph G. Prove that the symmetric difference of C and C' decomposes into cycles.

I know that the symmetric difference of C and C' contains only the edges that are in exactly one of C or C'. Since both C and C' are cycles, so d(v) for all v in V(G) must be even. So the difference would include a bunch of edges whose endpoints have even degree. If the degree is at least 2, we have cycle(s). But what if degree = 0? I am not really sure if it could be 0. I need a leg up, please! Thanks.


In the context of a question like this one you are only interested in edges and it is convenient to 'disregard' vertices. After all you want the symmetric difference of two cycles that have exactly one vertex in common to be just the same two cycles: you do not want to 'subtract a vertex'. You also do not want to answer the question: how many vertices has the symmetric difference of a cycle with itself. So we will simply assume that you have some underlying set of vertices, some of which are spanning your cycles, but we do not care about the vertices.

This answers your question "But what if degree=0?": if the degree is 0, there are no incident edges, so we do not care.

For the rest you can follow the argument you already started: first show that all degrees in the symmetric difference of two cycles are even, then show that any graph with only even degrees decomposes into cycles. Let me know if you need help with any of these parts.

Note that your proof will in fact demonstrate a stronger result: you can have an arbitrary number of cycles, but as long as you only use the operations union and symmetric difference the result can be decomposed into cycles.

| cite | improve this answer | |
  • $\begingroup$ I believe the following catches everything, doesn't it? Thanks for your help. Note that since C and C′ are cycles, d(v) is even for all v ∈ V (C) and all v ∈ (V (C′). Let G′ = C∆C′. Note that G′ contains the set of edges which are in exactly one of C or C′. Hence all v ∈ (G′) are even, so by Proposition 1.2.27 (Every even graph decomposes into cycles), C∆C′ decomposes into cycles. $\endgroup$ – PhiB Sep 27 '13 at 15:06
  • $\begingroup$ The step "Hence all $v\in G'$" may be too big, but that depends on your teacher's taste. And I do not know anything about proposition 1.2.27 :). $\endgroup$ – Leen Droogendijk Sep 27 '13 at 15:15
  • $\begingroup$ But don't I have to show that all v ∈ (G′) are even for G′ = C∆C? I didn't know if I could go directly to all v ∈ (C∆C′) are even. The proposition statement is in the parentheses. $\endgroup$ – PhiB Sep 27 '13 at 15:32
  • $\begingroup$ I meant to say: you may need to give more evidence that all $v\in G'$ are even. $\endgroup$ – Leen Droogendijk Sep 27 '13 at 18:28
  • 1
    $\begingroup$ Will the following suffice to show that all vertices in G′ are even? Let v∈V(G′) and suppose v is incident only to edges in C. Then d(v) is clearly even. Similarly for v ∈ C′. If v is incident to edges in both C and C′, then v has degree 2,3,or 4. If v has degree 2, then both edges incident to v are in C ∩ C′, so v will have degree 0 in C∆C′. If v is incident to exactly one edge in C ∩ C′, then v will have degree 2 in C∆C′. Finally, if v is incident to no edges of C∩C′, then v will have degree 4 in C∆C′. Hence all v ∈ (G′) are even. $\endgroup$ – PhiB Sep 29 '13 at 17:22

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.