Well begun is half done: the computation of Eulerian paths

arXiv:2611.00818 · math.LO, math.CO · Submitted 2026-10-31 · Read on arXiv

math.LO, math.CO

Submitted: 2026-10-31

Updated: 2026-11-04

License: http://creativecommons.org/licenses/by/4.0/

The gist: We characterize the uniform computational strength of finding (one-way or two-way, directed or undirected) Eulerian paths in countable graphs.

Abstract

We characterize the uniform computational strength of finding (one-way or two-way, directed or undirected) Eulerian paths in countable graphs. In the one-way case, for both directed and undirected graphs, this problem is Weihrauch-equivalent to times N', where N' is the jump of closed choice on the natural numbers. This refines the proof-theoretic strength of the existence of a one-way Eulerian path given by the reverse mathematics framework. The N' component comes entirely from the difficulty of choosing a starting vertex: with a valid start prescribed, the problem is equivalent to, which also characterizes the degree of the two-way directed/undirected Eulerian path problem. We also study the complexity of orienting the edges of a graph while preserving the existence of a one-way/two-way Eulerian path. In the one-way case, this problem is not computable, and we prove that 2< W < W 2' 2 and at most W N. On the other hand, valid orientations are uniformly computable for two-way paths and for one-way paths with a prescribed valid starting vertex.

Related papers