How many Eulerian circuits from the node 0 are there in this graph?

Question

I am new to this field, and I face with a question that asks me to count how many Eulerian circuits start from node 0 in this graph. The answer from the book is 264 but I feel that the answer is wrong.

I have tried the Fleury's algorithm to count but after several steps, I started being confused.

Answer 1

Here are 18 patterns that work:

  0abcd0bdac0
  0abcd0cadb0

  0abc0dacdb0  0abcdb0cad0
  0abc0dcadb0  0abcdb0dac0
  0abc0bdacd0  0abcad0bdc0
  0abc0bdcad0  0abcad0cdb0

  0ab0cdacbd0  0abcdac0bd0
  0ab0cdbcad0  0abcdac0db0
  0ab0cadcbd0  0abcadc0bd0
  0ab0cbdcad0  0abcadc0db0

  0ab0cadbcd0  0abcadb0cd0
  0ab0cbdacd0  0abcadb0dc0

You can replace a, b, c, and d by the labels 1, 2, 3, 4 in any order, giving you 22*24=528 possible directed circuits. If you want undirected circuits (i.e. doing the sequence in reverse is considered to be the same circuit) then you have to divide this by 2 to give 264 undirected circuits.

When creating this list of patterns, I had to keep in mind that the two instances of the same symbol had to have at least 2 symbols between them, and that if you have xy in the sequence then you cannot have another xy nor a yx elsewhere. I placed the zeroes first of course, and then other letters.

Answer 2

Here's a hint: Due to the symmetry of the $K_5$ graph, the first two edges you take are completely arbitrary. So the number of paths remaining, and the graph structure left to traverse, is unchanged at that point. You have $12$ options to choose those first two points, so pick any two (e.g. 1 & 2) and start the count from there, then multiply by $12$ at the end.

Continuing from initial (0)12 path: Notice that nodes 3 & 4 are still indistinguishable in terms of connectivity. So assume for now that we will visit 3 before 4 (giving further $2\times$ symmetry):

• 03x4y3z40, where xyz is some ordering of "",1,2. (3 options)
• 314x0y4z0, where xyz is some ordering of "",2,3. (3 options)
• 34x0y4z0, where xyz is some ordering of "",{13},2. (3 options)
• 30a4cd4b0, where 2 goes at a or b and cd is 1,3 in some order (4 options)

giving $13\cdot 24=312$ options by my count.