I would like to know what bounds are available for counting the number of eulerian circuits in a graph. I understand it is a #P-complete problem to get an exact count, but I am just looking for an upper bound.
I can get a crude bound in terms of the characteristic of the graph,
$$
\chi(G) = |E| – |V| + 1.
$$
Claim: The number of eulerian circuits in a graph $G$ is bounded by $(3\chi(G)-1)!$
Proof: First, observe that every vertex of degree $1$ can be removed without decreasing the number of eulerian circuits, and without changing the characteristic (deleting the vertex removes one edge and one vertex). We can also merge edges that meet at vertices of degree $2$ without changing the characteristic or the number of eulerian circuits (this process may introduce edges with multiplicity). By performing these operations we can reduce any graph $G$ to a graph $G'$ with minimum degree at least $3$, with $\chi(G')=\chi(G)$, and so that $G'$ has at least as many eulerian circuits as $G$.
Let $E'$ and $V'$ be the number of edges and vertices in $G'$, respectively. Then by the minimum degree of $G'$,
$$
E' \geq \frac{3}{2} V'.
$$
Combining this with the equation
$$
\chi(G) = E' – V' + 1,
$$
we get the bound
$$
\chi(G) = E' – V' + 1 \geq \frac{V'}{2} + 1
$$
and so
$$
E' = \chi(G) + V' + 1 \leq 3\chi(G) – 1.
$$
An eulerian circuit of $G'$ is in particular a permutation of the edges of $G'$, of which there are at most $(3\chi(G)-1)!$.
—
I feel that this argument is rather lossy, especially in the last step where I count eulerian circuits by permutations of edges. I assume that there are better bounds known, and this is what my question is about.
Question: What other bounds are available? In particular, is it known whether a bound
of the form $C \chi(G)!$ holds?
Best Answer
One bound is the following: if the graph has degree sequence $d_1,d_2,\dots,d_n$, then the number of Eulerian circuits is at most $$ \prod_{i=1}^n \frac{d_i!}{2^{d_i/2} (d_i/2)!} $$ Here, $\frac{d_i!}{2^{d_i/2} (d_i/2)!} = (d_i-1)(d_i-3)(d_i-5)\dotsm(3)(1)$ counts the number of ways to partition the $d_i$ edges out of the $i^{\text{th}}$ vertex into $\frac{d_i}{2}$ pairs. Each Eulerian circuit gives such a partition at every vertex: whenever you enter along an edge and leave along another, those edges get paired. But not all pairings correspond to a single closed circuit.
For a fixed number of vertices and edges, this bound is maximized by making the degrees as unbalanced as possible. If it were allowed, we'd make a single vertex with $|E|$ loops at it, and $|V|-1$ isolated vertices. You don't seem to be allowing isolated vertices (because there'd be no dependence on $\chi(G)$ in that case; by adding isolated vertices, you can make $\chi(G)$ arbitrarily small) so it's best to have $|V|-1$ vertices of degree $2$ and one vertex of degree $2|E|-2|V|+2 = 2\chi(G)$.
For such a graph, the upper bound above simplifies to $\frac{(2\chi(G))!}{2^{\chi(G)} \chi(G)!}$, and therefore this is also a general upper bound. In fact, the actual number of Eulerian circuits can also be approximately that high. If you have a "flower-shaped" graph where $\chi(G)$ cycles meet at a single vertex, a constant fraction of ways to pair up the edges at the central vertex produce an Eulerian circuit.