Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Given a connected graph with minimum degree 3 and a set of edges in this graph, I wish to find the number of decompositions of this edge set into cycles of the graph. I use decompositions in the sense that an edge in the set can be part of multiple cycles that the set is decomposed into. I know that this edge set is constructed by taking the union (not disjoint) of cycles of the graph, but I want to know how many other possible sets of cycles I could have taken the union of to get the same edge set. This might not be analytically possible but an algorithm to do this would be awesome.

share|cite|improve this question
You're after an edge cycle cover of your graph (rather than a "decomposition"). – Douglas S. Stones Nov 1 '12 at 12:32

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.