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

  • 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!2019-05-18
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
    Awesome! Thanks.2012-08-12