Can a non-oriented graph have more than one Eulerian cycle?

Question

I know that my question is more about graphs than programming but, I like the community here which is very active and you guys may have work with graphs.

So here Im wondering if the set of the Eulerian cycle of a non-oriented graph can contain more than one.

Thanks

Answer 1

The cycle is called Eulerian, iff it contains all edges, exactly one time each. That means that Eulerian cycles can only differ by edge's order (I propose to exclude edge's cyclical permutations as trivial option).

It is possible to find Eulerian cycle, using Fleury's algorithm: in short, move as you like (throwing out the edges you went on), but do not cross the bridge until the whole component is done. "The bridge" is the edge which is the only remaining way between different graph's components.

The proposed algorithm is quite old and well-known, so I won't prove its correctness.

Now, it should be quite obvious that there are graphs containing many different Eulerian cycles.

Answer 2

Yes, they often do. Have a look at this example, which contains multiple disjunct edge circles - you can build many different Eulerian circles from them:

_{Taken from German Wikipedia, created by Chin tin tin}