Eulerian Paths in a Complete Graph $K_5$

Question

As the title suggests, I’m simply looking for a method to compute the number of Eulerian Paths in the complete graph $K_5$, where all paths start from the same node. Since there are 5 nodes, all Eulerian paths must be Eulerian circuits as well.

Thanks.

Answer 1

Without using fancy tools like the BEST theorem, we can figure out the problem using inclusion-exclusion.

At each vertex of $K_5$, we have $4$ edges. A circuit is going to enter the vertex, leave, enter, and leave again, dividing up the edges into two pairs. There are $\frac12 \binom42 = 3$ ways to pair up the edges, so there are $3^5 = 243$ ways to make this decision at every vertex.

Not all of these will correspond to an Eulerian circuit, because not all of them connect up the way we'd like. We could also see:

• Two $5$-cycles (first diagram below). There are $\frac{5!}{2 \cdot 5} = 12$ ways to choose a $5$-cycle, and they'll always go together, so we should subtract $6$.
• A $4$-cycle and some other stuff (second diagram below). There are $\binom{5}{4} \cdot 3 = 15$ ways to choose a $4$-cycle, and $3$ ways to decide what happens at the vertex it doesn't visit, so we should subtract $15\cdot3 = 45$.
• A $3$-cycle and some other stuff (third diagram below). There are $\binom 53 = 10$ ways to choose a $3$-cycle, and $3^2$ ways to decide what happens at the two vertices it doesn't visit, so we should subtract $10 \cdot 3^2 = 90$.

But $243 - 6 - 45 - 90 = 102$ is still wrong, because we've double-counted one case. It's possible to have $3$ components: a $4$-cycle and two $3$-cycles (last diagram above). If we've chosen the $4$-cycle, there is one way to pair up the edges at the unvisited vertex to get the two $3$-cycles as well, so there's $15$ such configurations. We've subtracted them three times instead of once, so we should add them back in twice, getting $102 + 30 = 132$.

Multiplying by the two possible orientations, we get $264$ oriented Eulerian circuits. If we know which node is the first, but not which edge is the first, we can also start with two possible edges out of that node, getting $528$ oriented Eulerian paths starting at that node ($2640$ oriented Eulerian paths total).