4
$\begingroup$

I know it doesn't have a Hamiltonian circuit because vertices c and f will be traversed twice in order to return to a. Just confirming this. I mainly want to know whether I have the definition of distinct Euler circuits in a graph right, and whether the graph below is an example of this, i.e. {a,b,c} and {f,g,h}, being the 2 distinct Euler circuits.

enter image description here

  • 1
    You are right about the graph not having an Hamiltonian Circuit. How do you define distinct Euler Circuits? An Euler Circuit uses all edges of the graph by definition, and thus they can not be distinct. But the order of traversal for the edges might be different. In the latter case, there are more than 2 different traversals.2012-08-12
  • 0
    If you use the definition, that two Eulerian Circuits are distinct if they are not exact reversals, there are still more than 3 distinct Eulerian Circuits. For example $(a,c,d,f,g,h,f,e,c,b,a)$, $(a,c,d,f,h,g,f,e,c,b,a)$ and $(a,c,e,f,g,h,f,d,c,b,a)$.2012-08-12
  • 0
    I see. Thanks for the great explanation!2012-08-12

3 Answers 3

0

To clarify statements above, Two Eulerian Circuits are distinct iff they are not reversals of one another and they are not cyclic shifts of one another. To see why the additional constraint is needed, consider two Eularian circuits from the above graph:

c, a, b, c, e, f, g, h, f, d

c, e, f, g, h, f, d, c, a, b

and note that these Circuits both start from the same vertex and are not reversals of one another. However, they are not distinct, because the second circuit is a 3-letter shift of the first one.

In practice, the easiest way to count distinct Eularian circuits is to find a vertex of degree 2 and count all Eularian circuits departing in a single direction, resulting in a count of 4 for the above graph. However, when no such vertex exists, care must be taken to avoid recounting the same circuit.

3

An Euler circuit by definition traverses every edge of the graph exactly once, so neither $\langle a,b,c\rangle$ nor $\langle d,e,f\rangle$ is an Euler circuit. Starting at $a$ and counting two circuits as the same if one is simply the reversal of the other, I get the following four distinct Euler circuits:

$$\begin{align*} &a,c,d,f,g,h,f,e,c,b\\ &a,c,d,f,h,g,f,e,c,b\\ &a,c,e,f,g,h,f,d,c,b\\ &a,c,e,f,h,g,f,d,c,b \end{align*}$$

You are correct about the lack of a Hamilton circuit in this graph and the reason for it.

  • 0
    agreed. Thanks!2012-08-12
2

As you correctly state, the graph has not Hamiltonian Cycle, since it has a cut vertex (actually it has two, namely $c$ and $f$).

Regarding the number of distinct Eulerian Circuits, there are more than two if you take the definition of distinct to be

Two Eulerian Circuits are distinct, iff they are not exact reversals of each other.

In this case, the three circuits

$$(a,c,d,f,g,h,f,e,c,b,a)$$ $$(a,c,d,f,h,g,f,e,c,b,a)$$ $$(a,c,e,f,g,h,f,d,c,b,a)$$

are examples of distinct Eulerian Circuits.

As stated in Brian's answer, there are exactly 4 distinct Eulerian Cycles, namely

$$a,c,d,f,g,h,f,e,c,b$$ $$a,c,d,f,h,g,f,e,c,b$$ $$a,c,e,f,g,h,f,d,c,b$$ $$a,c,e,f,h,g,f,d,c,b$$

To count these, and make sure there are no more than 4, look at the number of times the walk "crosses itself". Since there are only two vertices ($c$ and $f$) where such a crossing can happen, the number of crossings can be 0,1 or 2. There is only a single walk with no crossing, namely $$a,c,d,f,g,h,f,e,c,b$$

There is also only a single walk with two crossings, namely $$a,c,e,f,g,h,f,d,c,b$$

and there are two walks with a single crossing, the one with a crossing in $c$ $$a,c,e,f,h,g,f,d,c,b$$

and the one with a crossing in $f$ $$a,c,d,f,h,g,f,e,c,b.$$

  • 0
    See Brian's answer ; there are precisely four circuits, easily counted.2012-08-12
  • 0
    I never stated that I had found all circuits, just three as a counter-example to the statement of exactly 2 distinct circuits.2012-08-12
  • 0
    Agreeing with you, but I was just thinking you should look, graphs are fun. =)2012-08-12
  • 0
    Thanks guys. Working on a graph that meets the definition now.2012-08-12
  • 1
    So, removing d, e and f and connecting the g--h part to c so that there is one edge from g to c and another from h to c, with g and h connected, should give me what I want, right?. A graph with eaxctly 2 distinct Eulerian circuits (acdecba and abcdeca) and no Hamiltonian circuits. Please correct me if I'm wrong.2012-08-12
  • 0
    Yes, the graph you obtain is the butterfly graph http://en.wikipedia.org/wiki/Butterfly_graph, which has exactly two distinct Eulerian Circuits, and no Hamiltonian Circuit.2012-08-12
  • 0
    Awesome! Thanks.2012-08-12