WorksMathematics
Well begun is half done: the computation of Eulerian paths
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 , where 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 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 and . On the other hand, valid orientations are uniformly computable for two-way paths and for one-way paths with a prescribed valid starting vertex.
Introduction
An Eulerian path in a graph is a trail that traverses every edge exactly once. For infinite graphs, one distinguishes between one-way paths, indexed by , and two-way paths, indexed by . The classical Erdős-Grünwald-Weiszfeld theorem (see [15 Thm. 3.2.1]) provides a characterization of when a countable graph admits a one-way Eulerian path. Analogous characterizations can be obtained for one-way Eulerian paths on directed graphs [13 Thm. 1], and two-way Eulerian paths for undirected graphs [15 Thm. 3.2.2] and directed graphs [13 Thm. 2].
2020 Mathematics Subject Classification. Primary 03D30; Secondary 05C45, 05C63.
Key words and phrases. Weihrauch reducibility, Eulerian paths, infinite graphs, directed graphs.
The author thanks Jeffry Hirst and Alberto Marcone for useful conversations on the topics of the paper. ChatGPT-6 was used to explore the literature, as well as discuss and critically review some of the proof strategies, and polish the presentation. All suggestions were carefully assessed, and the author takes full responsibility for the correctness of the results.
Eulerian paths have been studied in computable graph theory and reverse mathematics. In [3 Thm. 1], the author observed that there are computable graphs with an Eulerian path, but no computable such path. In contrast, every highly recursive graph (i.e. a locally finite computable graph admitting a computable degree function mapping every vertex to the number of its neighbors) with an Eulerian path has a computable such path. This result was recently generalized to moderately computable graphs (i.e. computable graphs with a computable degree function ) in [7]. In [8], the authors study the computability of separating infinite graphs into infinite components and how the number of ends affects the complexity of finding infinite simple paths and deciding whether Eulerian paths exist.
From the point of view of reverse mathematics, it has been shown that, even for pre-Eulerian (i.e. satisfying the hypotheses of the Erdős-Grünwald-Weiszfeld theorem) locally finite graphs, the existence of an Eulerian path is equivalent to over [10 Thm. 12]. However, a closer look at the proof reveals that, while there is a computable graph such that every Eulerian path through computes , the proof of the existence of an Eulerian path through every pre-Eulerian graph uses , therefore leaving a gap.
In this paper, we use the framework of Weihrauch reducibility to analyze the uniform computational strength of the problem of finding (one-way or two-way) Eulerian paths through countable (directed or undirected) graphs.
Definition 1.1. Let EP be the problem that takes as input a countable undirected graph that has a one-way Eulerian path, and outputs a sequence of vertices forming a one-way Eulerian path, and let DEP be the analogous problem on directed graphs. We also write (resp. ) for the problem that takes as input a countable undirected (resp. directed) graph that has a two-way Eulerian path, and outputs a two-way undirected (resp. directed) Eulerian path .
We assume that a graph is represented via the characteristic function of its set of vertices and edges.
In Theorem 3.4, we show that
where is the limit operator on Baire space and is the jump of closed choice on (see § 2.1). This refines the proof-theoretic characterization obtained via the reverse mathematics analysis: while every computable graph has a -computable solution, no uniform -computable procedure produces one. We observe that the gap between EP (or DEP) and rests entirely on the complexity of finding the first vertex of the Eulerian path. Once such a vertex is found, the rest of the path can be obtained uniformly in the jump of the input (Theorem 3.2). This also gives an intuitive explanation of why, in contrast to what happens for one-way paths, finding two-way (directed or undirected) Eulerian paths is simpler (Theorem 5.2 and Theorem 5.4):
The similarity of the directed and undirected constructions suggests a second question: can we computably orient an undirected graph while preserving the existence of a (one-way or two-way) Eulerian path? In § 4, we study the Weihrauch degree of the problem OrientEP of computing an orientation of the edges of a graph preserving one-way Eulerian paths. We obtain
The upper bound is obtained by showing that, for every undirected graph , we can uniformly compute a directed graph by orienting the edges of such that either or its global reversal is a valid solution for (Lemma 4.4). This implies, e.g. that . The obtained results separate OrientEP from other standard benchmarks in the Weihrauch lattice.
Once again, the complexity of OrientEP can be explained in terms of the complexity of finding the starting vertex of the path. In contrast, the problem OrientEP of orienting the edges of an undirected graph so that the resulting directed graph admits a two-way Eulerian path is uniformly computable (Theorem 5.6).
Background and notation
We briefly recall the main notions and fix the notation that will be used throughout the paper.
An undirected graph is a pair where is the set of vertices and is a set of unordered pairs of vertices, called edges. A directed graph is a graph where the edges are ordered pairs. To stress the difference between unordered and ordered edges between two vertices and , we use to denote the former and to denote the latter. In this paper, we will always assume graphs to be simple, i.e. graphs with no self-loops such that there can be at most one edge between any (ordered or unordered, depending on whether the graph is directed or not) pair of vertices. Given a graph , we use and to denote, respectively, the set of vertices and the set of edges of . We write for the degree of a vertex in , namely the number of neighbors of .
A path or walk through a graph is a (finite or infinite) sequence of vertices of such that, for each , the edge (or in case is directed) is in . Since we are working with simple graphs, a path uniquely identifies a sequence of edges. A trail is a path where no edge is repeated. A finite trail is called closed or open according to whether the initial and final vertices are the same or not. A ray is an infinite or finite and open trail with no repeated vertices. A cycle is a closed (non-empty) trail with at least one edge and no repeated vertices except for its endpoints. An Eulerian path is a trail that uses each edge and goes through each vertex. We distinguish between one-way Eulerian paths, namely Eulerian paths of the form and two-way Eulerian paths, i.e. Eulerian paths of the form .
There are well-known results that characterize exactly the graphs that admit Eulerian paths. To state them, we first introduce the following definitions: given a graph and a set of edges , we define as the graph obtained by removing all edges in from , as well as every vertex that remains isolated after the removal of . In symbols:
Theorem 2.1 (Erdős-Grünwald-Weiszfeld [15 Thm. 3.2.1]). A countable graph has an infinite one-way undirected Eulerian path iff
is connected,
has at most one odd-degree vertex, and if it has none then it has at least one infinite-degree vertex,
for every finite set of edges , has exactly one infinite connected component.
The characterization for directed graphs requires distinguishing whether an edge incident to a vertex is incoming, namely it is of the form for some vertex , or outgoing, namely it is of the form for some vertex . We write and for the number of incoming and outgoing edges at , respectively.
We say that a directed graph is weakly unbiased if, for every , the set of edges entering is infinite if and only if the set of edges leaving is infinite. We say that is strongly unbiased1 if it is weakly unbiased and, whenever the sets of edges entering and leaving are both finite, their cardinalities differ by at most 1.
For each directed graph , we define the underlying undirected graph of as the undirected graph defined as follows: where we can assume, modulo reindexing the vertices of , that every is a fresh vertex not in . The edges of are obtained by splitting each edge in two using and then removing the orientation. In symbols: . The reason why each edge is first split into two is to retain the fact that may contain the edges and , hence removing the direction while preserving the edges would result in a multigraph.
Theorem 2.2 (Nash-Williams [13, Thm. 1]). Let be a countable directed graph and let . Then admits a one-way directed Eulerian path starting from iff all the following conditions hold:
The underlying undirected graph of admits a one-way (undirected) Eulerian path,
For every vertex ,
with the convention that .
is weakly unbiased.
We also mention the characterizations of when an undirected/directed graph admits a two-way Eulerian path.
Theorem 2.3 (Erdős-Grünwald-Weiszfeld [15, Thm. 3.2.2]). A countable graph has an infinite two-way undirected Eulerian path iff
is connected,
has no odd-degree vertex,
for every finite set of edges , has at most two infinite connected components. Moreover, if for any , contains an even number of edges incident to , then has exactly one infinite connected component.
Theorem 2.4 (Nash-Williams [13, Thm. 2]). A countable directed graph admits a two-way directed Eulerian path iff all the following conditions hold:
The underlying undirected graph of admits a two-way (undirected) Eulerian path,
is strongly unbiased.
Observe that the two conditions in the previous theorem imply that, in a directed graph with a two-way directed Eulerian path, each vertex must satisfy .
Weihrauch reducibility
We briefly recall the main definitions on Weihrauch reducibility. For a more comprehensive presentation of Weihrauch reducibility, we refer the reader to [5].
Given , we say that is Weihrauch reducible to , and write , if there are two computable functionals and such that, for every ,
We call and the forward and backward functionals, respectively. These definitions can be extended to multi-valued functions on represented spaces by requiring that both and work on names of the objects. However, spaces like , , , or , as well as combinatorial objects like graphs or trees, admit a canonical representation as elements of . In these cases, with a small abuse of notation, we can identify an object with its name. In particular, as anticipated in the introduction, a graph is identified with the characteristic function of and . One-way or two-way paths are canonically represented as elements of . We think of as a discrete space (hence, in terms of representations, it can be identified with ).
The Weihrauch degrees form a distributive lattice with a bottom element () and no top element. The join and meet operators can be obtained, respectively, by lifting the following two operators on multi-valued functions to the degree structure:
, where .
, where .
The framework of Weihrauch reducibility supports a wide range of operators on computational problems, enabling the study of the uniform computational strength of natural combinations and modifications of existing problems. We briefly introduce the ones that will be relevant for this paper.
The parallel product is the problem with defined as . It corresponds to the idea of being able to use both and in parallel. The parallel product can be generalized to the countable case: we define the parallelization of a problem as the problem whose domain is the set of sequences of elements in and . To capture the idea of using and in series, we introduce the compositional product as follows: let be an effective presentation for all partial continuous functions with domain. We define
The parallel product, parallelization, and compositional product lift to Weihrauch degrees. There are also many natural operators that are not degree-theoretic. The jump of a problem is the problem whose input is a sequence in converging to some , and .
For every partial multi-valued function , its total continuation or totalization ([14]) is the total multi-valued function defined as
The strong total continuation of ([11]) is the total multi-valued function defined as
The difference between and is that an answer for the latter comes with the indication of whether , whereas this is not the case for the former. Neither of the two operators lifts to the Weihrauch degrees.
When studying the uniform computational strength of problems, it is common to compare them with benchmark problems, whose Weihrauch degree is well-studied and can be used as a reference.
For a metric space , is the problem that maps a convergent sequence in to its limit. We omit the subscript if . It is well-known that , where is the discrete space with two elements ([4, Thm. 13.5]). A convenient way to use is via the equivalence ([5, Thm. 11.6.7]), where is defined as iff . In other words, can be used to answer a or question, and can solve countably many of these questions in parallel. Similarly, the problem can be used to answer a or question, and (see e.g. [5, Thm. 11.6.5] and the proof of [16, Thm. 7.2]).
The choice problems are an important family of benchmarks: they intuitively describe the complexity of finding a point in a non-empty set. This complexity depends on the representation and the topological properties of the set. The formal definition of the closed choice problem is usually given in the more general context of represented spaces, but for the purposes of this paper, we can give the following (Weihrauch-equivalent) definition: for or the problem takes as input a non-empty represented by a formula (i.e. the input is a relation such that iff, for all , ), and produces . It is known that (see e.g. [5, Prop. 11.7.18]).
The problem is particularly important as being reducible to ([5, Thm. 11.7.13]) corresponds to being computable with finitely many mind-changes [5 Prop. 11.6.1]. It is known that [5 Thm. 11.6.7]. In comparison, is significantly weaker, as is Weihrauch-equivalent to weak König’s lemma, namely the problem of finding a path in an infinite tree . We will be especially interested in the problems and . A convenient way to describe them is the following: for or , is the problem that takes as input a non-empty defined by a formula, and produces . It is known that is Weihrauch-equivalent to the pigeonhole principle for singletons and two colors (see [6, Fact 2.3 and Prop. 3.4]).
Finally, we introduce the problem defined as
This will be useful to obtain an upper bound for the problem (see Definition 4.1 below). It is known that ([14, Prop. 24]).
Some results
We conclude this section with a few observations explaining why the techniques available in the literature do not directly yield a characterization of the uniform computational strength of finding an Eulerian path.
As mentioned in the introduction, every highly recursive or moderately computable graph that admits a (one-way or two-way) Eulerian path has a computable such path ([3, Thms. 2 and 3] and [7, Thm. A]). In fact, both results relativize to and the degree function . We also observe that Theorems 2 and 3 in [3] are uniform constructions, whereas the one-way case in [7 Thm. A] requires the additional knowledge of whether the graph has an odd-degree vertex.
Let be the function that takes as input a graph and a vertex and returns . Let also be the restriction of to locally finite graphs.
Proposition 2.5. .
Proof. To show that and we proceed as follows: for any graph and any vertex , first compute an enumeration of (possibly with repetitions). Then, we can build the set
Observe that if (which is always the case if is locally finite), then , hence we can use to pick a point . Given such a bound , we can compute by computing the size of . Conversely, if then . In this case, the answer of contains the information that is empty, which implies that .
To prove the reductions and observe that, given , we can compute the function mapping to the least number not enumerated outside of by stage . We can build a graph on whose edges are all and only those of the form where is such that . Observe that iff is eventually constant with value iff is finite. Besides, counts the changes of , so, if this is a finite number, then it allows us to compute .
Finally, it is known that as (the last equivalence follows e.g. from [16 Thm. 7.12]).
The above proposition can be adapted so that, in the proof of the reductions and , we always build a graph that admits a one-way or two-way Eulerian path.
Corollary 2.6. The restriction of to locally finite graphs is Weihrauch-equivalent to .
Proof. For the upper bound, let be a locally finite graph admitting a one-way Eulerian path. In light of [3 Thm. 2], in order to compute an Eulerian path through a given locally finite graph, it is enough to compute the function mapping every vertex to its degree. By the previous proposition, this can be done uniformly using .
The converse reduction is implicit in the direction (3) (1) of the proof of [10 Thm. 12].
With minor modifications, the above arguments can be adapted to the case of directed graphs. In fact, Proposition 2.5 can be adapted to show that the map is Weihrauch-equivalent to if each vertex has a finite number of incoming edges, and it is Weihrauch-equivalent to in the general case. An analogous characterization holds for the map . In particular, knowing that for every and every , is finite iff is finite, we obtain that the restriction of to locally finite graphs is Weihrauch-equivalent to .
These observations show that any approach to bounding the uniform computational strength of or that begins by computing the degree function (or both the in-degree and out-degree functions in case of directed graphs) would yield an upper bound at the level of (or above). In light of the rest of the paper, such an upper bound would not be optimal.
Similar considerations apply to the case of two-way undirected Eulerian paths. Indeed, as noted in [10 Sec. 3], the argument for the one-way Eulerian paths can be adapted to two-way undirected Eulerian paths. An analogous argument for two-way directed Eulerian paths does not seem to have been explicitly presented in the literature.
One-way Eulerian paths
For the sake of readability, we split the characterization of the Weihrauch degree of EP and DEP as follows: we first show the lower bound (Lemma 3.1). Then, for the upper bound, we show that starting from a prescribed vertex simplifies the problem of finding a one-way (directed or undirected) Eulerian path (Theorem 3.2). These facts, together with a technical lemma (Lemma 3.3) are then combined in the proof of Theorem 3.4.
Lemma 3.1. and .
Proof. We only show that . The reduction to EP builds the same graph, with the only difference being that the edges are undirected.
Let be an input for () and be a subset of . We represent as a sequence in such that .
We define a graph as follows (see Figure 1). We use disjoint computable sets of labels for the backbone, the vertices , and auxiliary vertices. The graph has a ray-like backbone where every backbone vertex is connected to via two paths of length 2 going in opposite directions.
Figure 1. The construction of the directed graph .
We will attach two different types of gadgets to this backbone. One will help us decide each LPO instance and the other will give us a solution to .
The first one is (essentially) the same gadget used in [10 Thm. 12]: when we first see that for some , we pick two fresh indexes and and attach a triangle to , oriented as .
To solve the -instance, for each we define a dedicated vertex (we choose so that, knowing , we can uniformly compute ) and attach it to a sufficiently large even backbone vertex unused so far by a triangle , where each is new. Whenever we find a new such that , we add another such triangle, using a fresh auxiliary vertex and a sufficiently large backbone vertex not used by any so far. Notice that iff .
Let us now show that admits a one-way directed Eulerian path. Let be the underlying undirected graph of . Observe that iff , and otherwise it has even degree. In fact, for every , . Besides, the fact that guarantees that at least one infinite-degree vertex exists. Observe also that deleting any finite set of edges leaves with exactly one infinite component: indeed, for a sufficiently large backbone vertex , the backbone tail beyond remains connected, and each backbone vertex before can have at most 1 triangle attached (whether a connection to some or a witness for the -th LPO instance). By Theorem 2.1, this shows that admits a one-way Eulerian path. It remains to show that is weakly unbiased. Observe first that its edges can be partitioned into finite directed cycles (either triangles or diamonds). For every , each such cycle has equally many edges entering and leaving . Summing over the cycles shows that the sets of edges entering and leaving have the same cardinality, hence is weakly unbiased. In particular, for every , Theorem 2.2 implies that there is a one-way directed Eulerian path through starting from .
Let be a one-way Eulerian path through . Since every vertex has the same incoming and outgoing degree, for some . This is because the starting vertex of the path must satisfy . Therefore knowing lets us uniformly compute an answer for .
To decide whether , we wait until has traversed all four backbone edges incident to . Then iff the path traverses the triangle . Indeed, the existence of such triangle implies that we have found such that . Conversely, if the path does not traverse the triangle, it means it has never been added: if the triangle is added to the graph but not traversed after visiting the four edges of then it would be disconnected from the rest of the graph, hence unreachable, against the fact that is an Eulerian path. This shows that we can uniformly compute the answer to every LPO-instance, and therefore conclude the proof. □
Observe that, in the previous argument, the answer to the -instance is determined solely by the initial vertex of the Eulerian path. This is no coincidence: the next result shows that specifying a valid starting vertex leaves a problem solvable using alone.
Theorem 3.2. Let (resp. ) be the problem that takes as input a pair , where is an undirected (resp. directed) graph, , and admits a one-way Eulerian path starting from , and returns a one-way undirected (resp. directed) Eulerian path through starting from . Then
Proof. The reductions and can be obtained by simplifying the construction in the proof of Lemma 3.1 as follows (see Figure 2): given an instance for LPO, define a directed graph so that it contains a ray (we connect and directly instead of via a diamond) and, when we first see that contains a 1, we add a triangle , for some nodes with sufficiently large index. The construction is the same in the undirected case: simply remove the orientation of the edges.

Figure 2. The construction for the reduction .
It is apparent that admits a one-way Eulerian path starting from . Besides, we can find the solution to by checking if the path visits immediately after or if it instead visits the triangle first.
Let us now show that . Let . As a consequence of Theorem 2.1, a finite trail starting at is extendible to a one-way Eulerian path iff the final vertex of has an unused incident edge and is connected (see [7 Thm. 3]). We show that these two conditions are uniformly relative to and , hence we can use to check them in parallel for every . Fix a finite trail and assume without loss of generality that . Checking if has an unused incident edge in is clearly relative to and . For the second condition, let
be the set of vertices in that are the endpoints of some edge not in . Since is connected, every connected component of contains a vertex in . In particular, is connected iff is connected in . Since is , the latter condition is relative to and .
Using , we can then uniformly compute a one-way Eulerian path through inductively by unbounded search: fix an enumeration of and let . At each stage , we search for some finite trail that is extendible to an Eulerian path and that visits . By the inductive hypothesis, such exists and the information given to us by allows us to find one. The limit of gives us a one-way Eulerian path through .
The proof of follows a similar strategy: let be an instance of . Using Nash-Williams’s theorem (Theorem 2.2), we can show that a finite directed trail starting from is extendible iff
the final vertex has an unused outgoing edge and
the underlying undirected graph of is connected.
Clearly, both conditions are necessary. To see that they are sufficient, observe that they imply that the underlying undirected graph of has a one-way Eulerian path (as above) and removing finitely many edges preserves weak unbiasedness. Since is a directed trail, for every vertex there is such that and . The same holds for if (hence, in particular, we obtain ). Otherwise, (as the first edge goes out of but there is no previous edge going to ) and
This shows that and satisfy the hypotheses of Theorem 2.2 and hence admits a directed one-way Eulerian path starting at .
The rest of the proof follows as in the undirected case: the two conditions above are uniformly relative to and , hence we can use to check them in parallel for every . Then, we can uniformly compute a directed one-way Eulerian path through starting from proceeding inductively by unbounded search while ensuring that we visit each edge.
Lemma 3.3. For every problem with codomain , .
Proof. Without loss of generality, assume . The reduction is immediate ([5 Prop. 11.5.7]), hence we only need to show the converse reduction. Let be a valid input for . We show that we can solve it using . We use the -th instance of to check if there is such that, in steps, produces a prefix of a sequence such that for some , .
Notice need not produce a convergent sequence if . On the other hand, if then and, for every there is such that stabilizes after stage . In particular, knowing some solution for , we can uniformly compute by searching, for each , for the first such that the -th instance of returns .
We are now ready to characterize the Weihrauch-degree of EP and DEP.
Theorem 3.4. .
Proof. The fact that is a lower bound for both problems is given by Lemma 3.1. The two reductions and follow a similar strategy: we first use (as it is known that and is closed under compositional product ([5, Thm. 11.7.53(1)})) to find a starting vertex for a (one-way) Eulerian path. We then use to obtain the rest of the path (using Theorem 3.2). This shows that both EP and DEP reduce to , and the claim follows by Lemma 3.3.
In the undirected case, let . Observe that checking if is odd is a uniformly condition relative to and , as it is equivalent to
If there is a vertex with odd degree, then use to choose the unique such vertex (as suffices to choose an element from a given subset of ). Otherwise, there must be a vertex with infinite degree, hence we use to choose from the set of vertices with infinite degree (which is uniformly relative to ).
In the directed case, let . We can use to check if there is a vertex such that . Indeed, this condition is equivalent to check if there are a vertex and two finite sets of edges such that , and (resp. ) contains all and only the edges in incoming to (resp. outgoing from) . In particular, this is uniformly relative to . If such a vertex exists, we can use to find it. Otherwise, we can use to choose from the set of vertices such that (which is uniformly relative to ).
Corollary 3.5. and .
Proof. Simply follows from the fact that there is a computable instance of whose solution is , while every computable instance of has a solution.
Corollary 3.6. Both EP and DEP are closed under parallel product, but not parallelizable nor closed under compositional product.
Proof. Since both and are closed under parallel product, so are EP and DEP. To show that EP and DEP are not closed under parallelization nor compositional product, it is enough to observe that , which can be proved using e.g. [5 Props. 11.6.12 and 11.6.14].
Orienting the edges
Definition 4.1. Let OrientEP be the problem that, given , returns such that the map is a (computable) bijection.
It is not hard to show that OrientEP is not uniformly computable.
Proposition 4.2. .
Proof. Let be an instance of . We build a graph as follows: at stage 0, let , and we add the edge to . Intuitively, we are building a ray, where the direction of the ray (left or right) is determined by the current element of the input sequence.
At stage , if , we add the edge and define , . Symmetrically, if , we add the edge and define , .
Since the sequence is eventually constant with value , exactly one of its values is extended infinitely often, so is a ray. The only orients as iff , uniformly computing the limit.
We can obtain the separation as a corollary of the next stronger result (as ):
Proposition 4.3. . Proof. Assume towards a contradiction that via the functionals . Notice that, for each input for , we can uniformly compute a guessing function such that, for each , is the least number not enumerated outside of by stage . In particular, .
To obtain a contradiction, we build a graph so as to force the guessing function to not have a limit. The graph is built iteratively as follows: at each stage , the approximation of is a graph consisting of a finite number of finite cycles going through the vertex and a finite ray containing . Let be the least number not enumerated outside of by stage . Without loss of generality, we can assume that, in steps, both computations and only query the oracle on edges whose endpoints are at most . This is useful so that later changes to the approximation of preserve earlier computations.
We start at stage with being the graph with two vertices and connected by an edge. The construction alternates between two different phases. We start in Phase 1.
Phase 1 In this phase, the ray is of the form for some . We check if , in steps, commits to the orientation of any edge as . If this does not happen, we add the edge , go to the next stage and remain in Phase 1. Otherwise, we add the edge and we move to Phase 2 and go to the next stage.
Phase 2 The ray is for some . We add the edge . We also check if , in steps, commits to the orientation of any edge as . If this does not happen, we go to the next stage and remain in Phase 2. Otherwise, we close the loop by adding the edge . We also add the edge , then move to Phase 1 and go to stage .

Figure 3. The two phases of the construction and the closing of the loop. Previously completed loops at 0 are omitted. Arrows on edges indicate the orientations produced by .
Observe that the construction must alternate between the two phases infinitely often. Indeed, if from a certain stage on, the construction remains in Phase 1, then the resulting graph is a ray with finitely many attached cycles (hence and the backward functional never orients the edges of the ray away from the origin . Clearly, no edge of the ray can be oriented toward (otherwise there cannot be any Eulerian path), hence it means that never produces an orientation for any edge of the ray, against the fact that witnesses a Weihrauch reduction. The case when the construction remains in Phase 2 is symmetric.
This shows that the resulting graph is the union of countably many cycles whose only vertex in common is (which therefore has infinite degree), therefore admits an Eulerian path.
To conclude the proof, it is enough to notice that every change from Phase 1 to Phase 2 forces to change guess. Indeed, assume otherwise and let be the current guess. When we close the loop, has committed to orienting an edge away from on each of its two sides. Therefore, regardless of how the remaining edges are oriented, there must be a vertex in the loop other than with two incoming edges and no outgoing one. Since this vertex has degree in , the resulting directed graph cannot admit an Eulerian path, against the fact that witnesses a Weihrauch reduction. Hence the guesses must change infinitely often, contradicting the convergence of .
We now work towards producing an upper bound for OrientEP. We will show that OrientEP . To show that OrientEP , we first need the following lemma.
Lemma 4.4. There is a computable procedure that, given a graph , computes a directed graph by choosing an orientation of the edges in such that either or .
Proof. The idea is to orient the graph locally, partitioning its edges into finite directed closed trails and at most one remaining directed trail (which could be finite, one-way infinite, or two-way infinite). The hypothesis that admits a one-way Eulerian path guarantees that the searches in the construction succeed. We will then show that the resulting orientation is weakly unbiased and that every vertex is balanced, with the possible exception of the unique odd-degree vertex of . If there is such a vertex , the correct global direction is the one satisfying ; otherwise, both and will admit a one-way directed Eulerian path.
We now show how to define the orientation (which yields the directed graph ). Let be an enumeration of . At each step, we maintain a finite directed open trail , which we aim to extend at either endpoint. Start with being an arbitrary orientation of . At stage , let be the least unoriented edge yet. We search for a finite directed trail that only includes unoriented edges and that satisfies one of the following:
includes and is a closed trail edge-disjoint from ;
includes and can be prepended or appended to to form an open directed trail;
can be appended to to form a closed trail.
In case (1), defines an orientation of its edges. We define and go to the next stage. Similarly, in case (2), we define as the directed trail obtained by prepending or appending to . Then, we define and go to the next stage. Finally, in case (3), we have obtained a closed directed trail. As in (1), we orient the mentioned edges as specified by the obtained closed trail. Then, we define , where is the first edge not oriented so far, and go to the next stage.
We now show that the search succeeds. Suppose that, at stage , none of (1), (2), or (3) is possible. Let and . Let , where is the set of edges not oriented by stage . Observe that committing to the orientation of a finite closed trail preserves the degree parity of each vertex. Similarly, the degree parity is preserved for every vertex in different from . In symbols:
Let be the connected component of containing .
The failure of (2) and (3) implies that contains neither nor . Besides, the failure of (1) implies that is infinite. Indeed, recall that can have at most one odd-degree vertex. If were finite then all of its vertices would have even degree, since the sum of the degrees of vertices in a finite graph is always even. In particular, would admit a closed Eulerian trail [15 Thm. 3.11]. Such a trail, once oriented, would contradict the failure of (1).
By Theorem 2.1, is the unique infinite connected component of . Let and be the connected components in of and respectively. In particular . Assume towards a contradiction that . Within , deleting the already oriented edges changes degree parity only at . Since the finite graph has an even number of odd-degree vertices, an odd number of its vertices must have odd degree in . In particular, contains an odd-degree vertex of . The same argument applies to , giving two distinct odd-degree vertices of , a contradiction. This shows that and therefore (3) can be satisfied, which is a contradiction.
Since each stage of the construction is well-defined, every edge is eventually oriented. The construction yields an edge-decomposition of the resulting graph into a family of finite directed closed trails and at most one remaining directed trail , which may be finite, one-way infinite, or two-way infinite.
We now show that either or admits a one-way directed Eulerian path. Observe that each closed directed trail contributes equally to the in-degree and out-degree of each vertex. The same holds for every vertex in different from the endpoint(s). At each endpoint, the contributions of differ by one, so any finite-degree endpoint has odd degree in , while every infinite-degree vertex has infinite in-degree and out-degree.
To show that (and hence ) is weakly unbiased, fix . Each closed directed trail has equally many edges entering and leaving , since either is contained in or is contained in , or every entrance in is followed by an exit. Likewise, along , the edges entering and leaving alternate: indeed, assume is infinite (otherwise it does not affect weak unbiasedness) and one-way. If the tail of is contained in or in , then the set of edges of that enter and leave are finite. Otherwise, divides in infinitely many finite directed trails , each one being a maximal consecutive subtrail of entirely contained in or in . Each has an incident edge entering and an incident edge leaving ( is an exception as it only has an incident edge leaving or has an incident edge entering ), hence they do not affect the weak unbiasedness of . The case when is a two-way directed trail is analogous. This shows that both and are weakly unbiased.
If has no odd-degree vertex, both orientations satisfy Theorem 2.2, starting at any infinite-degree vertex. Otherwise, there is such that is odd. Then and . In particular, exactly one of and satisfies Theorem 2.2 starting at .
Theorem 4.5. .
Proof. Given a graph , apply Lemma 4.4 to compute two orientations and of such that at least one of them admits a one-way directed Eulerian path. By the proof of Lemma 4.4, iff there is a vertex of finite degree such that . This is a condition relative to the input graph (see also the proof of Theorem 3.4). Hence the non-empty set
is uniformly relative to , and suffices to choose a valid orientation. ▫
As a corollary, we obtain e.g. that , since [6 Prop. 7.4]. We now show that . The following observation is a simple consequence of [12 Lem. 7] (see also [9 Thm. 8.4.2]).
Lemma 4.6. Let . If has no odd-degree vertex then it admits an edge-decomposition into finite cycles.
Proof. By [9 Thm. 8.4.2], it is enough to show that has no finite odd cut, i.e. there is no set such that the set of edges with exactly one endpoint in is finite and is odd. Fix and as mentioned, and suppose that is finite. Since is connected, removing leaves only finitely many connected components, and exactly one of them is infinite (Theorem 2.1). Hence one side of the cut, say , is finite. Every vertex in has finite even degree, hence, letting be the set of edges between two vertices in , we have . Therefore is even, as required. ▫
The proof of Lemma 4.4 can be adjusted to show that, if we are given both a graph and a vertex such that admits a one-way Eulerian path starting from , then we can computably choose which one between and admits a directed Eulerian path. However, we will prove a more general lemma that will simplify the proof of OrientEP Sort.
We say that a function is an enumerating function for a set if . In other words, checking if is a c.e. condition relative to .
Lemma 4.7. There is a computable procedure that, given a graph and an enumerating function for , computes .
We first explain the strategy behind the construction. By Lemma 4.6, every graph with no odd-degree vertex admits an edge-decomposition into finite cycles. A closer inspection of the proof readily reveals that the decomposition is effective. However, if there is an odd-degree vertex, a graph with an odd-degree vertex can only be edge-decomposed into , where each is a finite cycle and is a finite or one-way infinite trail. In this case, we use to decide the orientation of so that the resulting directed graph is in .
Proof. Let be an enumeration of . At each stage , we maintain a finite directed trail , starting with . If is already oriented by stage , we just define and go to the next stage. Let be the subgraph obtained from by removing the oriented edges and isolated vertices. We search in parallel for one of the following:
a finite cycle in containing ;
a stage such that has enumerated a vertex by stage . If such is found, we search for a finite trail starting at and containing such that extends and .
In case (1), we orient cyclically and go to the next stage with . In case (2), we orient pointing away from and go to the next stage with .
We now show that the search always succeeds. If has no odd-degree vertex, then case (2) never occurs, and the claim follows by Lemma 4.6. Assume instead that, at stage , we find such that is enumerated by by stage . Let be the final vertex of , taking if is empty. Observe that every finite-degree vertex of different from has even degree, while is odd if . Indeed, removing cycles preserves degree parity, and removing a trail from to changes parity only at its endpoints when these are distinct. If the endpoints coincide, or the trail is empty, the degree parity at is unchanged.
Hence the connected component of containing is infinite: if , this is immediate. Otherwise, a finite would have exactly one odd-degree vertex, which is impossible. By Theorem 2.1, is the unique infinite component of . If belongs to , there is a finite trail in starting at and containing . Appending this trail to gives a satisfying (2). Otherwise, the component containing is finite with all degrees even, so belongs to a finite cycle and (1) applies. Thus the search succeeds in both cases.
This shows that every edge is eventually oriented. We now prove that the resulting directed graph admits a one-way directed Eulerian path by showing that it satisfies the hypotheses of Theorem 2.2. Clearly the underlying undirected graph of has an Eulerian path, and the same argument used in the proof of Lemma 4.4 shows that is weakly unbiased. If has no odd-degree vertex, the construction gives an edge-decomposition into finite directed cycles. In this case, every vertex satisfies . Otherwise, let be the unique odd-degree vertex of . The construction gives an edge-decomposition into finite directed cycles and a finite or right-infinite directed trail starting at . Observe that every directed trail contributes equally to the in-degree and out-degree of each vertex, except for its endpoint(s). If is right-infinite, this implies that the only unbalanced vertex is (for which ). If is finite, we notice that its final vertex must have infinite degree. Indeed, suppose that . If , then contributes an odd number of edges incident to , while every closed trail contributes an even number. Hence is odd, against the fact that is the only possible odd-degree vertex of . If then is closed (possibly trivial), hence is even, against the fact that is odd. Thus the degree condition holds, completing the proof.
We can notice that the construction in the previous Lemma can be adapted to show that, given and a vertex such that has an Eulerian path starting from , we can uniformly compute a solution for . Indeed, the same proof applies whether has odd or infinite degree.
Theorem 4.8. .
Proof. By Lemma 4.7, it is enough to show that, given , we can use to compute an enumerating function for . Let be the set of pairs such that is odd and lists exactly the neighbors of , without repetitions. This set is uniformly relative to . Fix an enumeration of and define as the least pair that is not enumerated outside of by stage . We define the input for as
Observe that if has an odd-degree vertex, then eventually stabilizes at a pair such that has odd degree and is a list of the neighbors of . Otherwise, every guess is eventually refuted, and . In particular, changes its value finitely many times iff has an odd-degree vertex.
Let . Observe that if has no odd-degree vertex, then contains infinitely many zeroes and . Otherwise, , where is the total number of changes of .
In particular, given , we can compute an enumerating function as follows: we output as long as contains zeroes. Once the first in is found, using we can compute the final value of , and hence the unique odd-degree vertex of .
Theorem 4.5 and Theorem 4.8 immediately yield . We will now show that the reduction is strict. For the sake of readability, we first isolate the following lemma.
Definition 4.9. Given a directed graph , we can uniformly compute an enumeration of all finite directed cycles in . For each finite , we define recursively as follows: and is the directed graph obtained by reversing the orientation of the -th cycle in , and .
Lemma 4.10. For any , any and any two , there is such that is defined and agrees with on the orientation of the first edges of .
Proof. Fix as in the hypotheses. Observe that, for every for which is defined, is a valid solution for , as reversing the orientation of a cycle does not affect the existence of a one-way directed Eulerian path. We recursively define a string as follows: we start with . At each stage, we have a set of all the edges in with index on which and agree. Let be the first edge with index on which and disagree (if no such exists we are done).
Consider the set
If then there is a cycle of proving the claim. We define and go to the next stage. We show that leads to a contradiction. Indeed, for a directed graph and , let
Clearly, hence, by definition of , it is finite. Since is weakly unbiased, this implies also that is finite. Since is finite, Theorem 2.1 implies that (i.e. deleting the undirected edges in from ) has exactly one infinite component.
Let if does not contain the infinite connected component of , and otherwise. Since , it follows that there are finitely many edges with an endpoint in . In particular, every one-way directed Eulerian path eventually leaves permanently. Since both and are in , we have that for ,
This can be proved using e.g. [13 Lem. 4]. This, together with (which follows from the fact that has the same boundary in ), implies that and . This, in turn, implies that .
Since , it follows by definition of that . However, by construction, and disagree on the direction of the edge , hence , which is a contradiction. □
Theorem 4.11. .
Proof. The reduction follows from (Theorem 4.5), (Theorem 4.8), as is the meet in the Weihrauch lattice.
For the separation, suppose towards a contradiction that via . Recall that a solution for is of the form where determines whether or . It is convenient to use and therefore think of an instance of as a binary sequence , and a solution for is a number that appears infinitely often in .
For every instance of , we write for the graph defined by and for the two orientations of computably obtained by Lemma 4.4. Consider the two computations for . By Lemma 4.4, at least one of the two computations produces a valid solution for .
We first claim that if, for every input , every valid canonical orientation yields a answer, then . This would contradict Theorem 4.8, as [14 Prop. 24] but [5 Thm. 11.7.54].
To prove the claim, assume that, for every input and , if then . Given an instance of , produce the graph and let . In parallel for every such that is defined (see Definition 4.9), we run the computations until we find some such that . Notice that the search is guaranteed to terminate by Lemma 4.10, because at least one canonical orientation is valid and, by assumption, its backward computation returns a -answer. Besides, every enumerated is a valid solution for , hence this establishes .
This shows that we can choose an input and such that . We now diagonalize against by showing that there is an input for on which the reduction fails to produce a valid answer. Let be sufficiently large so that .
We first show that there are two strings , such that, for some , . Indeed, consider both computations for . If there are no as above, then . This implies that is the correct one instead. By continuity, there are sufficiently long prefixes and on which produces either for some or for some . In the first case, set and , otherwise set and . In both cases, we are forcing to produce the wrong answer on every input of the form where . Hence, letting be the number of zeroes in , there is such that .
By continuity, this implies that the pair fails to produce the correct answer for , against the definition of Weihrauch reducibility.
To conclude the proof, fix and as above. In this case, letting , we obtain that for every , does not produce a valid answer.
We distinguish two cases:
if, for some and some sufficiently large , , then, we let and .
if, for some sufficiently large , , then, by continuity, there are and such that (such must exist because contains finitely many zeroes). We define and .
In both cases, we obtain that neither nor are valid solutions, as required. □
Two-way Eulerian paths
We now turn our attention to the case of two-way Eulerian paths.
Definition 5.1. Let (resp. ) be the problem that takes as input an infinite countable undirected (resp. directed) graph that has a two-way Eulerian path, and outputs a sequence of vertices forming such a path.
Recall that, by Theorem 3.4, . Intuitively, the first half () comes from the difficulty of “starting the path”, while the second half () is the complexity of finding “the tail of the path”. Obviously, there is no “start” in a two-way Eulerian path, and indeed we can show that . For the sake of readability, we split the proof in two results, one for the undirected and one for the directed case.
Theorem 5.2. .
Proof. The reduction can be proved with a simple modification of the graph used in the proof of (Theorem 3.2), where the only difference is that the vertices are now arranged so as to form a two-way line .
Let us now show that . Let be an instance of . By [7 Prop. 4.13], a finite trail with initial vertex and final vertex is extendible to a two-way Eulerian path iff
there are distinct edges incident to and , respectively;
every connected component of contains or .
We show that these conditions are uniformly relative to and . The first condition is relative to and , since we can search for two distinct unused edges incident to the endpoints. The second condition is equivalent to requiring that, for every , one of the following holds:
(I) contains all the edges incident to , or
(II) there is a finite trail from to or in .
To see that, let . Assume first that (2) holds and let . If has an incident edge that is not contained in , then , hence (2) implies that there is a finite trail from to either or . Conversely, fix a connected component of . Since is connected, contains some vertex of : take any path from to . For this , (I) fails (as otherwise would not be in ), hence (II) holds, and therefore contains either or .
Observe that the conditions (I) and (II) are, respectively, and relative to and . This implies that, using , we can check which finite trail is extendible to a two-way Eulerian path.
To conclude the proof, we observe that such a path can be computed (uniformly) by greedy search while ensuring that all the edges are visited: fix an enumeration of . Let . We start with and . At stage , we have defined a finite trail with endpoints and . We search for a finite trail extending such that
is extendible to an infinite two-way Eulerian path.
extends by adding at least one additional edge at each end.
By the inductive hypothesis, such a trail exists, and, in the limit, this construction yields a solution for .
To characterize the degree of , we first prove an auxiliary result.
Lemma 5.3. Let be a directed graph admitting a two-way directed Eulerian path. Let be a finite directed trail and let and . Define the graph as the directed graph obtained from by adding a fresh vertex and the edges and .
Then extends to a two-way Eulerian path in iff the underlying undirected graph of is connected.
Proof. Suppose first that extends to a two-way directed Eulerian path in . Replacing the occurrence of in this path by gives a two-way directed Eulerian path in . In particular, the underlying undirected graph of is connected.
Conversely, suppose that the underlying undirected graph of is connected. We show that admits a two-way directed Eulerian path. This implies that extends to a two-way Eulerian path in : indeed, every two-way Eulerian path in must traverse the edges . Replacing the finite trail with gives a two-way Eulerian path in extending .
Let be a two-way Eulerian path in and let be a finite subtrail of containing every edge of . Define and . Without loss of generality, we can assume (extending if necessary). Consider the finite directed subgraph of such that
Observe that, since the two trails and have the same endpoints, for every vertex
Besides, and . This implies that can be decomposed into finitely many edge-disjoint cycles and a finite open directed trail from to . This can be proved e.g. applying [2 Ex. 4.8] to the graph obtained by adding a fresh auxiliary vertex and the edges and to .
Let be the two-way directed trail obtained by replacing with in . We extend by attaching each cycle in stages as follows: at each stage , we have a list of unused cycles. Since is connected there is such that, for some unused cycle (with the assumption that ), has some vertex in common with . Choose such that belongs to . We define by visiting between and . More formally, modulo reindexing , we can assume . We define
We then label as used and go to the next stage. Each stage is possible because is connected, and the procedure terminates after stages. The trail is a two-way directed Eulerian path through , which concludes the proof.
Theorem 5.4. .
Proof. The reduction is obtained by a straightforward modification of the construction in Theorem 3.2 (see also the proof of Theorem 5.2): arrange the vertices in a two-way line .
For the converse reduction, let be an instance of . For each nonempty finite directed trail , let be the graph obtained by replacing with as in Lemma 5.3. We show that connectedness of the underlying undirected graph of is uniformly relative to and .
Observe that is connected iff, for every , at least one of the following holds:
every edge of incident to belongs to ;
there is a finite undirected path in from to .
For the forward implication, if (1) fails, then is a vertex of , so connectedness gives (2). Conversely, let be the underlying undirected graph of . Since is connected, every connected component of contains a vertex . By construction, every such vertex has an edge that does not belong to . In particular, by (2), is connected to in . Since, clearly, and are connected to , this shows that is connected.
Conditions (1) and (2) are respectively and relative to and , and hence, since is finite, checking if is connected is uniformly in and . We can therefore use to check which extend to a two-way Eulerian path.
To complete the proof, fix an enumeration of . At each stage, we greedily search for an extension of the finite trail built so far such that
is extendible,
contains ,
extends by adding at least one edge at each end.
We start with . Since the search is guaranteed to succeed at each stage. In the limit, we obtain a two-way trail passing through each edge, and therefore it is a valid solution for .
Similarly to the case of one-way Eulerian paths, we can consider the problem of orienting the edges of an undirected graph while preserving the existence of a two-way (directed or undirected) Eulerian path.
Definition 5.5. Let be the problem that, given , returns such that the map is a (computable) bijection.
Unlike what happens for the case of one-way Eulerian paths, finding an orientation of the edges of an undirected graph so that the resulting directed graph admits a two-way Eulerian path is computable.
Theorem 5.6. The problem OrientEP is computable.
Proof. Let . We claim that the algorithm used in Lemma 4.4 to build the directed graph gives a valid solution for . Recall that the construction builds an edge-decomposition , where each is a finite directed closed trail, could be finite or infinite, and is a trail and could be empty, finite, one-way infinite, or two-way infinite. The construction maintains a finite directed open trail at each stage, and tries to progress the edge-decomposition by searching for a finite directed trail that only includes edges that have not been oriented so far such that satisfies one of the following ( is the first edge that has not been oriented by stage ):
includes and is a closed trail edge-disjoint from ;
includes and can be either prepended or appended to to form an open directed trail;
can be appended to to form a closed trail.
To show that the search always succeeds, let be the undirected graph of edges that have not been oriented by stage , and let be the connected component of containing . Let also and be the two endpoints of . As in the proof of Lemma 4.4, if neither (1), (2), nor (3) is possible, then , , and is infinite. Observe now that both and have unused incident edges, since the construction has removed an odd number of edges incident to each of them, while their degrees in are even or infinite. Assume that and belong to different connected components. The connected component of is infinite: if it were finite, would be the only odd-degree vertex in , therefore the sum of the degrees of the vertices in would be odd, which is impossible for a finite graph. Likewise, the connected component of is infinite. Together with , this would give three infinite components after deleting finitely many edges from , contrary to Theorem 2.3. Thus lie in the same connected component of , and (3) is possible.
To conclude the proof, we need to show that is strongly unbiased. Fix . Let (resp. ) be the set of edges entering (resp. leaving ). Observe that, if we define, for a directed subgraph ,
then
Since each has equally many edges entering and leaving , . Consequently, if they are both infinite then both and are infinite. Assume now that they are both finite. Observe that, along a directed trail , the edges entering and leaving alternate. Therefore, either , and hence both and are infinite, or . This shows that is strongly unbiased.
Since (and hence the underlying undirected graph of ) admits a two-way Eulerian path, by Theorem 2.4 we conclude that admits a two-way directed Eulerian path, and hence .
Manlio Valenti
Department of Computer Science, Swansea University, Swansea, SA1 8EN, UK
Email address: [email protected]
References
- [1]Andrews, Uri, Lempp, Steffen, Marcone, Alberto, Miller, Joseph S., and Valenti, Manlio, A jump operator on the Weihrauch degrees, Computability 14 (2025), no. 2, 73–94, doi:10.1177/22113568241309768. MR 5000365DOI
- [2]Bang-Jensen, Jørgen and Gutin, Gregory, Digraphs, 2 ed., Springer Monographs in Mathematics, Springer-Verlag London, Ltd., London, 2009, doi:10.1007/978-1-84800-998-1, Theory, algorithms and applications. MR 2472389
- [3]Bean, Dwight R., Recursive Euler and Hamilton paths, Proceedings of the American Mathematical Society 55 (1976), no. 2, 385–394, doi:10.2307/2041731. MR 416888DOI
- [4]Brattka, Vasco, Gherardi, Guido, and Marcone, Alberto, The Bolzano-Weierstrass Theorem is the jump of Weak König’s Lemma, Annals of Pure and Applied Logic 163 (2012), no. 6, 623–655, doi:10.1016/j.apal.2011.10.006. MR 3650357
- [5]Brattka, Vasco, Gherardi, Guido, and Pauly, Arno, Weihrauch Complexity in Computable Analysis, Handbook of Computability and Complexity in Analysis (Brattka, Vasco and Hertling, Peter, eds.), Springer, Cham, Jul 2021, doi:10.1007/978-3-030-59234-9_11, pp. 367–417. MR 4300761DOI
- [6]Brattka, Vasco and Rakotoniaina, Tahina, On the uniform computational content of Ramsey’s theorem, The Journal of Symbolic Logic 82 (2017), no. 4, 1278–1316, doi:10.1017/jsl.2017.43. MR 3743611DOI
- [7]Carrasco-Vargas, Nicanor, Infinite Eulerian paths are computable on graphs with vertices of infinite degree, Computability 14 (2025), no. 2, 95–110, doi:10.1177/22113568251359095. MR 5000366
- [8]Carrasco-Vargas, Nicanor, Delle Rose, Valentino, and Rojas, Cristóbal, Paths, ends and the separation problem for infinite graphs, Discrete Applied Mathematics. The Journal of Combinatorial Algorithms, Informatics and Computational Sciences 386 (2026), 139–155, doi:10.1016/j.dam.2026.02.004. MR 5029912
- [9]Diestel, Reinhard, Graph theory, 6 ed., Graduate Texts in Mathematics, vol. 173, Springer, Berlin, 2025, doi:10.1007/978-3-662-70107-2. MR 4874150DOI
- [10]Gasarch, William and Hirst, Jeffry L., Reverse mathematics and recursive graph theory, Mathematical Logic Quarterly 44 (1998), no. 4, 465–473, doi:10.1002/malq.19980440405. MR 1654281DOI
- [12]Nash-Williams, C. St. J. A., Decomposition of graphs into closed and endless chains, Proceedings of the London Mathematical Society. Third Series 10 (1960), 221–238, doi:10.1112/plms/s3-10.1.221. MR 113810
- [13]———, Euler lines in infinite directed graphs, Canadian Journal of Mathematics 18 (1966), 692–714, doi:10.4153/CJM-1966-070-2. MR 200197
- [14]Neumann, Eike and Pauly, Arno, A topological view on algebraic computation models, Journal of Complexity 44 (2018), 1–22, doi:10.1016/j.jco.2017.08.003. MR 3724808DOI
- [15]Ore, Oystein, Theory of graphs, American Mathematical Society Colloquium Publications, vol. Vol. XXXVIII, American Mathematical Society, Providence, RI, 1962, doi:10.1090/coll/038. MR 150753DOI
- [16]Soldà, Giovanni and Valenti, Manlio, Algebraic properties of the first-order part of a problem, Annals of Pure and Applied Logic 174 (2023), no. 7, Paper No. 103270, 41, doi:10.1016/j.apal.2023.103270. MR 4583071DOI
