{"id":"arxiv/2611.00818","url":"https://arxiv.org/abs/2611.00818","tags":["math.LO","math.CO"],"score":0,"title":"Well begun is half done: the computation of Eulerian paths","domain":"math.LO","source":"arxiv","authors":["Manlio Valenti"],"reviews":0,"subject":"math.LO","summary":"We characterize the uniform computational strength of finding one-way Eulerian paths in countable graphs. For both directed and undirected graphs, this problem is Weihrauch-equivalent to $\\mathsf{lim}\\times\\mathsf{C}_{\\mathbb{N}}'$, where $\\mathsf{C}_{\\mathbb{N}}'$ is the jump of closed choice on the natural numbers. This refines the proof-theoretical strength of the existence of an Eulerian path given by the reverse mathematics framework. The $\\mathsf{C}_{\\mathbb{N}}'$ component comes entirely from the difficulty of choosing a starting vertex: with a valid start prescribed, the problem is…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-10-31","reactions":{}}