The Eulerian graph recurrence conjecture for bd(G)

Proof, with a stronger identity for the entire Eulerian polynomial.

Let $G=(V,E)$ be a finite loopless Eulerian graph, let $n=|V|\ge1$, and choose a balanced orientation $D$: orient an Euler tour in each nontrivial connected component. Thus

$$\operatorname{indeg}_D(v)=\operatorname{outdeg}_D(v) =\frac{\deg_G(v)}2 \qquad(v\in V).$$

For an ordering $\pi=(v_1,\ldots,v_n)$, write $\operatorname{des}_D(\pi)$ for the number of arcs directed against the ordering, so that

$$A_D(t)=\sum_{\pi\in\mathfrak S(V)} t^{\operatorname{des}_D(\pi)}.$$

Cyclically rotate an ordering by moving its final vertex $v$ to the first position. Comparisons not involving $v$ are unchanged; the descent contribution from the edges at $v$ changes from $\operatorname{outdeg}_D(v)$ to $\operatorname{indeg}_D(v)$. These are equal. Therefore

$$\operatorname{des}_D(v,v_1,\ldots,v_{n-1}) =\operatorname{des}_D(v_1,\ldots,v_{n-1},v).$$

Every cyclic-rotation orbit of an ordering of $n$ distinct vertices has exactly $n$ elements, and for every fixed $v\in V$ exactly one ordering in that orbit ends at $v$. Since $t^{\operatorname{des}_D(\pi)}$ is constant throughout each orbit,

$$A_D(t) =n\sum_{\pi_n=v}t^{\operatorname{des}_D(\pi)}.$$

When $v$ is the final vertex, its outgoing arcs contribute exactly $\operatorname{outdeg}_D(v)=\deg_G(v)/2$ descents, and all other descents belong to the induced orientation $D-v$. Hence the following stronger polynomial identity holds simultaneously for every vertex:

$$\boxed{\; A_D(t) =n\,t^{\deg_G(v)/2}A_{D-v}(t) \qquad(v\in V). \;}$$

In particular, if $\nu(H)=|A_{\vec H}(-1)|$, which is independent of the orientation $\vec H$, then

$$\boxed{\;\nu(G)=n\,\nu(G-v)\qquad\text{for every }v\in V.\;}$$

Consequently all vertex-deleted graphs have the same invariant, and summing gives the conjectured recurrence

$$\boxed{\; \nu(G)=\sum_{v\in V}\nu(G-v). \;}$$

The argument includes disconnected Eulerian graphs, isolated vertices, $n=1$, and the case $\nu(G)=0$. It also proves coefficientwise divisibility $n\mid[t^j]A_D(t)$ for every $j$.

In fact a signed strengthening holds for any orientation $D'$: cyclic rotation changes the descent parity by $\deg_G(v)$, which is even, and the same orbit argument gives

$$A_{D'}(-1) =n(-1)^{\operatorname{outdeg}_{D'}(v)} A_{D'-v}(-1) \qquad(v\in V).$$

Source: Celano, Sieger, and Spiro, Eulerian polynomials for digraphs, Combinatorial Theory 5 (2025), article 15, Conjecture 6.2, https://doi.org/10.5070/C65165026 ; https://arxiv.org/abs/2309.07240 .