Let G be a graph, and define nu(G) as the absolute value of A_D(-1) for any orientation D of G. An Eulerian graph is a graph in which every vertex has even degree. Eulerian graph recurrence conjecture. If G is an Eulerian graph, then nu(G)=∑_v nu(G-v). This recurrence could help give a combinatorial interpretation of nu(G) for arbitrary graphs. Computational evidence suggests it, but the paper does not establish it in general.

The Eulerian graph recurrence conjecture for bd(G)

About 3 years old · traced to 2023

Let $G$ be a graph, and define $\nu(G)$ as the absolute value of $A_D(-1)$ for any orientation $D$ of $G$ . An Eulerian graph is a graph in which every vertex has even degree. Eulerian graph recurrence conjecture. If $G$ is an Eulerian graph, then

\nu(G)=\sum_v\nu(G-v).

This recurrence could help give a combinatorial interpretation of $\nu(G)$ for arbitrary graphs. Computational evidence suggests it, but the paper does not establish it in general.

References

Primary source

Kyle Celano, Nicholas Sieger and Sam Spiro, “Eulerian Polynomials for Digraphs”, arXiv:2309.07240 (2023).

Posted 1 month ago

Progress summary

Refreshed 1 month ago

Claimed solved

A reader-written attempt claims a complete proof of the recurrence, but no independent verification or published confirmation has been found.

The conjecture asks whether every Eulerian graph satisfies $\nu(G)=\sum_v\nu(G-v)$ . Celano, Sieger, and Spiro recorded it as an open problem in their 2023 paper, building on work of Kalai and Even-Zohar.

Known results

Celano, Sieger, and Spiro (2023) prove $\nu(G)\leq\eta(G)$ for general graphs.
They prove the deletion inequality $\nu(G)\leq\sum_v\nu(G-v)$ .
Equality $\nu(G)=\eta(G)$ is proved for bipartite graphs, complete multipartite graphs, and blowups of cycles.
Their inductive method does not establish the conjectured equality in general.

Posted attempt

A reader-written argument claims a stronger identity, $A_D(t)=n\,t^{\deg_G(v)/2}A_{D-v}(t)$ for every vertex of an Eulerian graph, and derives $\nu(G)=n\nu(G-v)$ and hence the conjecture. It presents this as a complete proof, but the argument has not been independently verified and is not supported by a published source.

Current status (as of August 2026): The conjecture has a complete-proof claim but no verified resolution; the published literature establishes only the general inequality and special graph classes.

Sources

ProofThis solution needs a summarySee full solutionHide full solution

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 .