Author note (2026-11-02). The paper cited here, arXiv:2603.12894 (“Optimal Enumeration of Eulerian Trails in Directed Graphs”), is by Ben Bals, Solon P. Pissis, Matei Tinca. The name(s) this essay attributes it to (Rizzi, Tomescu) do not appear among the listed authors, so the attribution below is wrong or refers to someone else's earlier work; I have not worked out which. Found by a mechanical check of each essay's named authors against the arXiv author list.
An Eulerian trail traverses every edge of a graph exactly once. Counting them is a classical problem solved by the BEST theorem (de Bruijn, van Aardenne-Ehrenfest, Smith, Tutte), which reduces the count to a determinant over the graph's Laplacian. But listing them — producing each trail explicitly — is harder. The previous best algorithm by Conte et al. runs in O(m ยท z_T) time, where m is the number of edges and z_T the number of trails. Multiply the graph size by the output size.
Rizzi & Tomescu (arXiv:2603.12894) eliminate the multiplication. Their algorithm enumerates all z_T Eulerian trails in O(m + z_T) time — additive, not multiplicative. Read the graph once, then output each trail in constant amortized time per trail.
The method is direct: instead of building arborescences (spanning trees rooted at a vertex) and converting each to a trail via the BEST theorem's correspondence, they construct trails incrementally, backtracking only when necessary and reusing partial traversals. The simplicity is the point. The BEST theorem is elegant but indirect — it counts by establishing a bijection with arborescences. Enumerating through that bijection introduces overhead at each step. Bypassing the bijection entirely and working in trail space directly turns out to be both simpler and faster.
This is a recurring pattern in combinatorial algorithms: the counting formula that makes the mathematics beautiful introduces indirection that makes the computation expensive. The optimal algorithm doesn't use the theorem at all. It respects the structure the theorem describes — Eulerian graphs, balanced degrees, connectivity — without routing through the theorem's proof machinery.
Sometimes the theorem tells you what exists. The algorithm that finds it fastest doesn't need to know why.
Added 2026-11-06: the abstract of arXiv:2603.12894 (now v3) differs in its figures between the first version and the current one, so some differences described in the notes above may come from that revision and not from an error in the essay (I may have worked from the earlier version). This was found by a later mechanical comparison; I have not re-checked the essay claim by claim against the first version.