Give a formula for the number of closed Eulerian walks on the complete graph Kn.

Question

I believe a Eulerian walk must hit all edges on a graph, and a closed Eulerian walk must start and finish at the same vertex? This can only exist if all vertices are of even degree. So for all $Kn, \ n=even$, there are 0 closed Eulerian walks. For $Kn,\ n=odd$, there are ${n\choose 2}$ edges to work with. We can start with any edge first, have edge-1 for next choice, etc. So, ${n\choose 2}! = {total\ closed\ Eulerian\ walks}$?

This works for n=3, but for greater, there are many instances where you will get stuck, so not all ${n\choose2}!$ options will work. How can I correct this, or is there another obvious method I have missed entirely?

Answer 1

Yes, an Eulerian walk must same start and endpoints, except for $K_2$, otherwise the walk "uses up" an odd number of edges at some vertex, and an even number of edges at another vertex.

No, $\binom{n}{2}$ counts all the edges, and $\binom{n}{2}!$ counts all permutations of the edges, including permutations such as $$ (12,34,23,13,24,14,15,25,35,45) $$ when $n=5$, where the consecutive edges $12$ and $34$ do not share an endpoint, violating the condition that it's a walk. However, $\binom{n}{2}!$ gives an upper bound on the number

There's probably no straightforward formula: there's no formula given at Sloane's OEIS A135388 for Eulerian circuits, and enumeration is only complete up to $n=15$.

Answer 2

$$\ln \binom{n}{2}! \approx \left(\binom{n}{2} e^{-1}\right)^\binom{n}{2}$$ You can get a much tighter bound by observing that the path is of length $\binom{n}{2}$ but at each step you have at most $n-1$ decisions, so that the number of paths is bounded above by $$(n-1)^\binom{n}{2}$$

To get tighter still, there is an easy observation that there are at most $n$ occasions when you have $n-1$ choices, at most $n$ occasions when you have $n-2$ choices, etc., giving an upper bound of $$\prod_{i=1}^{(n-1)/2}(n-i)^n$$

To make the observation sharp, we need to consider that:

• The very first decision has $n-1$ choices, because we start from a vertex which has been entered 0 times and exited 0 times
• The next decision is already down to $n-2$ choices, because the edge we used to enter the vertex cannot be used to exit it
• The $i$th decision made in the start vertex has $n-1-2(i-1)$ options; the $i$th decision made in any other vertex has $n-2-2(i-1)$ options.

Since we're assuming $n$ is odd, we enter each vertex $(n-1)/2$ times and leave it $(n-1)/2$ times, so we take $(n-1)/2$ decisions in each vertex. Thus we get an approximation which should be much sharper: $$\prod_{i=1}^{(n-1)/2} (n-2i+1)(n-2i)^{n-1}$$

Comparing to the values in OEIS A135338, this overestimates by a fairly small factor: it gives exact results for $n=3$, and overestimates by a factor of $2.45$ for $n=5$, up to a factor of $13.6$ for $n=15$.