The Eulerian graph recurrence conjecture for bd(G)
Let be a graph, and define as the absolute value of for any orientation of . An Eulerian graph is a graph in which every vertex has even degree. Eulerian graph recurrence conjecture. If is an Eulerian graph, then
This recurrence could help give a combinatorial interpretation of for arbitrary graphs. Computational evidence suggests it, but the paper does not establish it in general.
References
- Kyle Celano, Nicholas Sieger and Sam Spiro, “Eulerian Polynomials for Digraphs”, arXiv:2309.07240 (2023).
Progress summary
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 . 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 for general graphs.
- They prove the deletion inequality .
- Equality 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, for every vertex of an Eulerian graph, and derives 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.
Solutions 1
This solution needs a summarySee full solution
Proof, with a stronger identity for the entire Eulerian polynomial.
Let be a finite loopless Eulerian graph, let , and choose a balanced orientation : orient an Euler tour in each nontrivial connected component. Thus
For an ordering , write for the number of arcs directed against the ordering, so that
Cyclically rotate an ordering by moving its final vertex to the first position. Comparisons not involving are unchanged; the descent contribution from the edges at changes from to . These are equal. Therefore
Every cyclic-rotation orbit of an ordering of distinct vertices has exactly elements, and for every fixed exactly one ordering in that orbit ends at . Since is constant throughout each orbit,
When is the final vertex, its outgoing arcs contribute exactly descents, and all other descents belong to the induced orientation . Hence the following stronger polynomial identity holds simultaneously for every vertex:
In particular, if , which is independent of the orientation , then
Consequently all vertex-deleted graphs have the same invariant, and summing gives the conjectured recurrence
The argument includes disconnected Eulerian graphs, isolated vertices, , and the case . It also proves coefficientwise divisibility for every .
In fact a signed strengthening holds for any orientation : cyclic rotation changes the descent parity by , which is even, and the same orbit argument gives
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 .