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.