On the complexity of the Eulerian path problem for infinite graphs
Nicanor Carrasco-Vargas Valentino Delle Rose Cristóbal Rojas



§ ABSTRACT 
    We revisit the problem of algorithmically deciding whether a given infinite connected graph has an Eulerian path, namely, a path that uses every edge exactly once.  It has been recently observed that this problem is D_3^0-complete for graphs that have a computable description, whereas it is Π_2^0-complete for graphs that have a highly computable description, and that this same bound holds for the class of automatic graphs. A closely related problem consists of determining the number of ends of a graph, namely, the maximum number of distinct infinite connected components the graph can be separated into after removing a finite set of edges. The complexity of this problem for highly computable graphs is known to be Π_2^0-complete as well. The connection between these two problems lies in that only graphs with one or two ends can have Eulerian paths. In this paper we are interested in understanding the complexity of the infinite Eulerian path problem in the setting where the input graphs are known to have the right number of ends. We find that in this setting the problem becomes strictly easier, and that its exact difficulty varies according to whether the graphs have one or two ends, and to whether the Eulerian path we are looking for is one-way or bi-infinite. For example, we find that deciding existence of a bi-infinite Eulerian path for one-ended graphs is only Π_1^0-complete if the graphs are highly computable, and that the same problem becomes decidable for automatic graphs. Our results are based on a detailed computability analysis of what we call the Separation Problem, which we believe to be of independent interest. For instance, as a side application, we observe that König's infinity lemma, well known to be non-effective in general, becomes effective if we restrict to graphs with finitely many ends.  


    


GraphEx: A Graph-based Extraction Method for Advertiser Keyphrase Recommendation
    Kamesh Madduri
    September 9, 2024
================================================================================





§ INTRODUCTION





 The study of infinite graphs from a computability point of view dates back to the seminal work of Manaster and Rosenstein <cit.>, and of Bean <cit.>, who initiated a research program devoted to understand the algorithmic complexity of deciding classical graph properties for families of graphs that have an algorithmic description. 
 How hard is to decide a given property depends on how strong is the given computable description of the graph, and the program consists on characterizing this relationship, for instance  according to the hierarchies of algorithmic complexity provided by computability theory. 

 
 A central notion in these works is that of a computable graph. Intuitively, an infinite graph is computable if there is an algorithm to decide whether or not  two vertices are connected by an edge. These works also introduced the idea of considering stronger notions of computability for graphs, namely highly computable graphs. Highly computable graphs correspond to the subclass of locally finite computable graphs for which, in addition, one can effectively compute the degree of each vertex. Intuitively, one can think of a highly computable graph as a graph for which there is an algorithm capable of drawing a certified picture of any of its finite portions. A third class of graphs, introduced much more recently <cit.>, is that of automatic graphs. These are graphs whose vertex set and adjacency relation can be described by finite automaton, and their algorithmic properties have been sistematically compared with those of computable and highly computable graphs (see <cit.>). 


The point of considering these stronger notions is that some problems may become easier for graphs with stronger algorithmic descriptions, and an important goal is to understand for which problems this is indeed the case. 
An interesting example is given by the coloring problem. While Bean constructed an example of a computable graph with chromatic number 3 that cannot be computably colored with any finite number of colors <cit.>, Schmerl proved that any highly computable graph with chromatic number k admits a computable coloring with at most 2k-1 colors (and that such bound is tight) <cit.>. 

Another particularly interesting example is the Eulerian path problem, which has a very long history in mathematics as it can be dated back to the famous problem of the seven bridges of Könisberg. In 1736, Euler solved this problem <cit.> by providing a characterization of those finite graphs possessing (what we now call) an Eulerian path, namely a path which visits every edge exactly once. Around two-hundred years later, Euler's characterization was extended to countably infinite graphs by Erdős, Grünwald and Vázsonyi <cit.>. From a computability perspective, it turned out that such result is non-effective for computable graphs, while it admits an effective version in the highly computable case. Let us call a graph Eulerian when it admits an Eulerian path: Bean <cit.> showed that, while there are computable Eulerian graphs for which every Eulerian path is non computable, a highly computable graph is Eulerian if and only if it has a computable Eulerian path –moreover, one can effectively compute (an index for) such a path given (an index for) the graph. See also <cit.> for a recent generalization of Bean's result. 

It is important to notice that Bean's result is rather unusual, being in stark contrast with other fundamental results in graph theory which are proven to be non-effective even when restricted to highly computable graphs. Notable examples are the Hall's marriage theorem <cit.>, Ramsey's theorem <cit.> and the existence of vertex or edge colorings of a certain size <cit.>.

A related question is that of deciding whether a given graph is Eulerian. This problem was shown to be D_3^0-complete (where D_3^0 denotes the class of sets which can be expressed as differences of two Σ_3^0 sets) for computable graphs, whereas the same question is only Π_2^0-complete in the case of both highly computable graphs or automatic graphs <cit.>[Notice that in his survey <cit.>, Gasarch states, without proof, that the existence of an Eulerian path in computable graphs was Π_3^0-hard and Σ_4^0, while the precise complexity was still unknown. Also,  Π_2^0-completeness of the same problem in the case of highly computable graphs is stated, without proof, in <cit.>.]. 

The proof of Π_2^0-completeness from <cit.> strongly relies on the classical characterization by Erdős, Grünwald and Vázsonyi <cit.>, which relates the existence of Eulerian paths to a certain topological property of graphs, namely, the number of ends of a graph. Indeed, according to this characterization, only graphs with one end can have one-way Eulerian paths, while only graphs with one or two ends can have bi-infinite (or two-ways) Eulerian paths. Notably, Kuske and Lohrey also showed that the problem of counting the number of ends of a graph is itself  Π_2^0-complete. Even if we know that the number of ends of a graph is at most two, deciding whether is has one or two ends is already a Π_2^0-complete problem. 



 §.§ Main results
 In this paper, motivated by a deeper understanding of how the complexity of these different problems interact, we fix the number of ends of a graph and ask whether the complexity of the Eulerian path problem changes. Interestingly, we find that leaving the number of ends out of the decision task makes the Eulerian path problem significantly easier. 

Theorem A. Determining whether a highly computable graph with one end has a one-way Eulerian path is Σ_2^-1-complete, whereas for two-ways Eulerian paths it is only Π_1^0-complete. On the other hand, for highly computable graphs with two ends, the problem attains precisely the m-degrees of Δ_2^0 sets. 



The situation for highly computable graphs is summarized in the Table <ref>.

We also ask the question for the  class of automatic graphs, for which the same Π_2^0-completeness bound holds in the general case. Surprisingly, we find that the complexity in this case decreases dramatically when restricted to graphs with only one end. 

Theorem B. Determining whether an automatic graph with one end has an Eulerian path is a decidable problem. 




These results are based on a detailed analysis of what we call the Separation Problem. This problem consists of determining the number of different connected components a graph gets separated into after removing a finite number of edges. Our main tool is a result stating the computability of the Separation Problem from a description of a highly computable graph plus some additional, non-uniform, finite information about it. This result, together with some other related observations, constitute our main technical contribution. As an amusing consequence of this analysis, we show that König's lemma is effective for graphs with finitely many ends: 

Theorem C. A connected, highly computable, and locally finite graph with finitely many ends is infinite if and only if it admits a computable infinite path.


On the other hand, we also provide an example of a highly computable infinite graph with only one end, for which every geodesic infinite path is uncomputable, showing some subtleties in this kind of questions.   







 §.§ Related work
 Besides the Eulerian Path problem, in his work <cit.> Bean also considered the case of Hamiltonian paths (those paths visiting each vertex of a given graph exactly once) and showed that Hamiltonian paths may be all uncomputable even for highly computable graphs. 
More recently, Kuske and Lohrey in <cit.> characterized the exact complexity of both the Eulerian path problem and the Hamiltonian path problem: these problems are, respectively, Π_2^0-complete and Σ_1^1-complete, and these bounds apply to highly computable as well as automatic graphs. As further evidence of the relevance of this kind of problems in computability theory, we would like to point out that a recent work by Jura, Levin and Markkanen <cit.>, extending the seminal work  by Gasarch and Lee <cit.>, considers a notion of effectivity for graphs that lies between computable and highly computable graphs. In particular, they show that for every non-computable Δ_2^0 oracle A, the ability to compute non-trivial neighborhoods in a graph (that is, A can compute the degree function of a graph which is not highly computable) is equivalent to the existence of A-computable graphs (i.e., computable graphs whose degree function is computable in A) which admit Eulerian paths but no computable Eulerian path. 



 §.§ Paper organization
 In <Ref> we briefly recall all the notions that will be relevant for our study. In <Ref> we introduce the Separation Problem, and develop a first set of technical results about its computability, which we directly use to prove Theorem C. Then in <Ref> we put this analysis together with some observations specific to the Eulerian path problem and prove Theorems A and B. Finally, in <Ref> we carry on a more in-depth analysis of the Separation Problem and establish a fairly complete classification result for it. 


 §.§ Acknowledgements

N. Carrasco-Vargas  was partially supported by ANID Doctorado Nacional/2020-21201185, ANID/ Basal National Center for Artificial Intelligence CENIA FB210017, and the European Union's Horizon 2020 research and innovation program under the Marie Sklodowska-Curie grant agreement No 731143.  V. Delle Rose was supported by the project PRIN 2022 Logical Methods in Combinatorics No. 2022BXH4R5 of the Italian Ministry of University and Research (MIUR). C. Rojas was supported by ANID/FONDECYT Regular 1230469 and ANID/Basal National Center for Artificial Intelligence CENIA FB210017.



§ PRELIMINARIES




 §.§ Graph theory

We consider undirected, simple graphs. That is, edges are non-ordered pairs of vertices and no loops or multiple edges between vertices are allowed. The set of vertices of a graph G is denoted by V(G), and its set of edges by E(G). Each edge joins a pair of vertices, and is said to be incident to each of the vertices it joins. Two vertices joined by an edge are called adjacent or neighbors. The degree of a vertex v, denoted _G(v), is the number of edges in G incident to v. A graph is said to be even when every vertex has even degree.

We will consider subgraphs that are induced  by sets of edges or vertices. We will often write A ⋐ B as an abbreviation for A is finite and A ⊆ B. Let V⊂ V(G). The induced subgraph G[V] is the subgraph of G whose vertex set is V, and whose edge set is {e∈ E(G) : e joins vertices in V}. We write G∖ V=G[V(G)∖ V]. Now let E⊂ E(G). The induced subgraph G[E] is the subgraph of G whose edge set is E, and whose vertex set  is {v∈ V(G) : v is incident to an edge in E}. We write G∖ E = G[E(G)∖ E].  

A path p in a graph is a sequence of adjacent vertices v_0,…,v_n. We call v_0 and v_n the initial and final vertices of p, respectively.  We say that p  visits the set of vertices {v_i| 0≤ i≤ n}, and the set of edges {e_i| i∈{0,…,n-1},  e_i  joins v_i to v_i+1}.  A graph is connected if every pair of vertices can be joined by a path. In a connected graph G, the distance d_G(v,w) between two vertices v and w is the length of the shortest path joining them, where the length of a path is the number of edges that it visits.  A connected component of a graph is a connected subgraph that is maximal for the subgraph relation. 

The following notion will be central for us.  

    The number of ends of a connected graph G is the supremum of the number of infinite connected components of G∖ E, where E ranges over all finite subsets of E(G).

Observe that the number of ends of a graph G may be infinite. We note that other ways of defining the number of ends of a graph exist, but they all coincide for locally finite graphs <cit.>. 


    We remark that, for the sake of clarity, in what follows we will restrict ourselves to study the case of graphs that are connected and locally finite. However, our definitions apply to connected graphs which are not necessarily locally finite, and many of our results extend straightforwardly to this more general case. We will explicitly point this out when appropriate. 







 §.§ Computability theory

Let us review some computability theoretical terminology which will be used throughout the paper. The notation we use is quite standard and follows mostly the textbook <cit.>. Note that we will often identify a set A ⊆ with its characteristic function A →{0, 1 } so that A(n)=1 n∈ A. For a set A we will write A to denote its complement. 

Given a partial computable function φ, it is understood that it is computed by some Turing machine, which we also denote by φ. We write φ_s to denote the outcome of (running the Turing machine) computing φ for s many steps: if such computation is successful, namely φ halts within s many steps, we write φ_s ↓, otherwise we write φ_s ↑. We also write φ↓ in case there is an s for which φ_s ↓, and φ↑ otherwise. Similarly, for a c.e. set W, we denote by W_s the set of its elements enumerated within s steps. 


It is well known that one can give a computable enumeration of all partial computable functions, as well as of all c.e. sets. Also, one can consider a computable enumeration (φ_e)_e ∈ of Turing machines without input and define the halting set = {e  φ_e ↓}.

In this paper we will make an extensive use of two notions of reducibilities among sets, both of them measuring, intuitively, the relative complexity of those sets. 

The first one is defined in terms of oracle Turing machines, namely Turing machines with an additional one-way read only tape: when φ is equipped with oracle Y, we write φ^Y and we mean that, for each n, the n-th cell of such tape contains a 1 if n ∈ Y, and a 0 otherwise.
Let A, B ⊆.
    A is Turing-reducible to B, denoted by A ≤_T B, if there is an oracle Turing machine φ such that φ^B(n) = A(n) for every n ∈. Moreover, if both A ≤_T B and B ≤_T A holds, we write A ≡_T B and say that A and B are Turing-equivalent.  

Notice that, by means of oracle Turing machines, one can define the halting set relative to any set Y, i.e. the set Y'={e: φ_e^Y ↓}. Therefore, it is possible to consider, for example, ∅”, the halting set relative to ∅' and, similarly, ∅^(n) for every n>0: in this way, one obtains a strictly increasing chain with respect to ≤_T, namely ∅ <_T ∅ ' <_T ∅”<_T …

Let us turn to the second notion of reducibility: 

    Given A, B ⊆, we say that A is many-one-reducible (or, simply, m-reducible) to B, and write A ≤_m B, if there is a computable function f → such that, for every n, 
    
    n ∈ A  if and only if f(n) ∈ B.

    If both A ≤_m B and B ≤_m A holds, A and B are said to be m-equivalent and we write A ≡_m B.

It is immediate to verify that both ≡_T and ≡_m are equivalence relations: the Turing-degree (respectively, the m-degree) of A ⊆ is the equivalence class of A with respect to ≡_T (respectively, ≡_m).

Reducibilities are closely related to the core idea of hierarchies, which group sets in increasing levels of difficulty. One which is widely used in computability theory is the so-called arithmetical hierarchy, whose levels are defined as follows. 

    Let A ⊆ and n≥0. 
 
    
  * A is Σ_n^0 if there is a computable relation R ⊆^n+1 such that, for all x,
    
    x ∈ A   if and only if ∃ y_1 ∀ y_2 … Q y_n R(x,y_1, …, y_n),

    where Q is ∃ if n is odd, and ∀ if n is even.  
    
  * A is Π_n^0 if A is Σ_n^0.
    
  * A is Δ_n^0 if it is both Σ_n^0 and Π_n^0.

Moreover, A set is said to be Σ_n^0-complete (respectively, Π_n^0-complete) if it is Σ_n^0 (Π_n^0) and for every Σ_n^0 (Π_n^0) set X it holds that X ≤_m A.


The arithmetical hierarchy is tied to the Turing degrees of the form ∅^(n) by the well-known Post's Theorem.
 For every n > 0, ∅^(n) is Σ_n^0-complete and ∅' is Π_n^0-complete. 

Moreover, for every n ≥ 0 and A ⊆:
    
        
  * A is Σ_n+1^0 if and only if A is c.e. relative ∅^(n);
        
  * A is Δ_n^0 if and only if A ≤_T ∅^(n).
    


We will also use the fact that Inf = {e   |W_e|= ∞} and Fin = {e   |W_e| < ∞} are, respectively, Π_2^0-complete and Σ_2^0-complete (see, e.g., <cit.>). 

Another notion we will use extensively is that of computable approximation of a set. 

    A computable approximation of A ⊆ is a computable function f ^2 →{0, 1 } such that, for all n:
    
        
  * lim_s f(n,s) exists (i.e. |{f(n,s)  f(n,s+1)}| < ∞), and
        
  * A(n) = lim_s f(n,s).
    

The following well-known result characterizes the Δ_2^0 sets precisely as those admitting computable approximations:

    A set A ⊆ is Δ_2^0 if and only if A has a computable approximation.

Using the characterization given by the Limit Lemma, it is possible to provide a hierarchy of the Δ_2^0 sets based on the number of mind changes in their computable approximations. This is known as the Ershov hierarchy: as proven in <cit.>, the whole hierarchy exhausts all Δ_2^0 sets. We will define only the initial levels of such hierarchy, which are the only ones playing a role in what follows, and refer the interest reader to the excellent survey <cit.>.

    Let n ≥ 0 and A⊆ be a Δ_2^0 set. We say that:
    
        
  * A is Σ_n^-1 (or n-c.e.) if there is a computable approximation f of A such that, for every x ∈, |{s   f(x,s)  f(x,s+1)| ≤ n. 
        
  * A is Π_n^-1 if A is Σ_n^-1.
        
  * A is Δ_n^-1 if it is both Σ_n^-1 and Π_n^-1.
    

The terminology n-c.e. is motivated by the following characterization, whose proof is straightforward.

    Let A ⊆. Then:
    
        
  * A is 0-c.e. if and only if A is computable.
        
  * A is n-c.e., with n=2k, if and only if there exist c.e. sets A_1 ⊇ A_2 ⊇…⊇ A_2k such that A = (A_1 ∖ A_2) ∪…∪ (A_2k-1∖ A_2k).
        
  * A is n-c.e., with n=2k+1, if and only if there exist c.e. sets A_1 ⊇ A_2 ⊇…⊇ A_2k+1 such that A = (A_1 ∖ A_2) ∪…∪ (A_2k-1∖ A_2k) ∪ A_2k+1.
    

The m-degrees of n-c.e. sets have been extensively studied in <cit.>: in particular, for each n > 0, one can prove the existence of a Σ_n^-1-complete set, namely a n-c.e. set C such that A ≤_m C whenever A is n-c.e.



 §.§ Computability for Graphs

We now recall some standard computability notions for countably infinite graphs.

    A graph G is computable when V(G) is a decidable subset of , and the adjacency relation is a decidable subset of ^2. A computable graph G is highly computable when it is locally finite  and the vertex degree function V(G)→ is computable. 



    The notion of highly computable graphs can be naturally extended to graphs which are not necessarily locally finite by requiring the vertex degree function to be computable as a function from V(G) →∪{∞}. 

    
    The notion of computable graph is strictly weaker than that of highly computable. In particular, decidability of the adjacency relation only allows to enumerate the set of neighbors of a vertex, and we need to know the degree of this vertex to be sure that no more neighbors can be added. Indeed, an easy example of a (connected and locally finite) graph which is computable but whose degree function is uncomputable is the following: let V(G) = and E(G) = { (x,x+1) | x ∈}∪{ (m, -n) | n = ⟨ m,s ⟩ and φ_m,s-1↑ and φ_m,s↓}, where (φ_e)_e ∈ is some fixed enumeration of all Turing machines without input and ⟨ ·  ,  · ⟩ is a fixed computable bijection of ^2 to . Notice that the degree of each vertex is either 2 or 3, but, for m >0, we have that d_G(m) = 3 if and only if φ_m halts. 

    Notice that, equivalently, we could define a highly computable (locally finite) graph as one for which there exists a computable function capable of drawing any finite portion of the graph: more precisely, G is highly computable if and only if there is a computable function f  V(G) ×→ which maps any pair (v,r) to (an index of) the finite graph G[{w ∈ V(G) | d_G(v,w) ≤ r}]. We also note that this characterization does not apply to the case of graphs which are not locally finite. 

    Finally, we say that a sequence (G_e)_e ∈ of highly computable graphs is uniformly highly computable if there are computable functions V, E and  with two inputs, such that 
    
    
  * V(e,v)=1  v ∈ V(G_e), 
  * E(e,⟨ v,w⟩)=1 {v,w}∈ E(G_e) and 
    
  * (e,v)=n  v ∈ V(G_e)  and _G_e(v)=n.
    



§ THE SEPARATION PROBLEM


Where does the hardness of the Eulerian path Problem comes from? From the classical result by Erdős, Grünwald and Vázsonyi <cit.>, we expect the number of ends of a graph to play a central role and, in fact, the proof behind the upper bound given in <cit.> shows that it is precisely deciding whether the graph has the right number of ends where the complexity lies.  


Recall that the number of ends of a graph corresponds to the maximal number of  different infinite connected components the graph can be separated into by removing a finite set of edges. The focus of this Section will be on characterizing the algorithmic complexity of what we call the Separation Problem: given a graph G and a finite set of edges E, to count the number of different infinite connected components of G∖ E.  Let us therefore start by introducing some vocabulary. 

 
Let G be a locally finite connected graph, and let E⊂ E(G)
be a finite set of edges. We denote by _G(E) the number
of distinct infinite connected components in G∖ E. We say
that E is separating or that it separates G when _G(E)≥2. We denote by G the collection of all separating finite sets of edges, and by G the collection of all finite sets of edges E⊂ E(G) such that _G(E) equals the number of ends of G. 



We note that a finite set of edges E belongs to G precisely when all the connected components of G∖ E have either 0 or 1 end. In particular, when G has infinitely many ends the set G is empty, and if G has only one end, then any finite collection of edges (including the empty one) belongs to G.   




Our goal will be to establish the algorithmic complexity of computing _G(E). As we shall see, while as a function of both G and E this is an upper-computable function in general, it becomes computable when we fix a graph G with finitely many ends and see it as a function of E alone. The results we present here will be crucial in <Ref>, where we study the complexity of the Eulerian Path Problem for infinite graphs. 







We start by showing that for graphs with finitely many ends, the quantity _G(E) can be computed in a non-uniform way, that is, by an algorithm which in addition to G and E, receives some suitable extra finite information about the graph G.


    There is a partial computable function which, when receiving as inputs a (program for a) highly computable graph G with finitely many ends, a finite set E ⊂ V(G), the number of ends of G and an arbitrary element W ∈G, outputs _G(E). 



    We start by exhibiting an algorithm, called 𝒜, that will be used several times in the course of this proof. The algorithm 𝒜 takes as input a program for an infinite and highly computable graph G with finitely many ends, the number k of ends of G, and an element W∈G. Thus G∖ W has exactly k infinite connected components.  The algorithm computes the set V of vertices in G∖ W that are incident to some edge from W, and then outputs a partition V=V_1⊔…,⊔ V_k⊔ F, where V_i is the set of vertices in V that lie in the i-th infinite connected component of G∖ W, and F is the set of vertices in V that lie in a finite connected component of G∖ W. 

    We now explain the process executed by 𝒜. It is clear how to compute the set V from the input, as the graph is highly computable. For each vertex v∈ V, we denote by C_v the connected component of G∖ W containing v. Now observe the following:
    
        
  * For every v∈ V, the property “C_v is finite" is c.e event, as this can be verified by computing finite portions of the graph G.
        
  * For every u≠ v in V, the property “C_u=C_v" is a c.e event, as this can be verified by finding a finite path in G from u to v, and which visits no edge from W.
    
    

    Our algorithm 𝒜 executes the individual algorithms for the finitely many c.e. events indicated above. That is: for each v∈ V, we wait to see whether C_v is finite, and for each pair of vertices u v∈ V, we wait until eventually we see that C_u=C_v. Knowing the number of ends of G, and since W ∈G, eventually these algorithms will provide enough information to write a partition V=V_1⊔…,⊔ V_k⊔ F as desired. At this point the algorithm 𝒜 stops and outputs this partition.  
    
    We now proceed to prove the claim in the statement.  
    Assume we receive as inputs some description of the highly computable graph G, a finite set of edges W ∈G, the number k of ends of G, and a finite set E ⊂ E(G). We will compute  a finite set of edges U satisfying the following conditions:
    
        
  * U contains E and W.
        
  * G[U] is connected.
        
  * For each pair of vertices  u,v in G∖ U that are incident to edges from U, and such that u,v lie in the same infinite connected component of G∖ U, there is a path from u to v that is completely contained in G[U∖ E].
        
  * G∖ U has exactly k infinite connected components, and no finite conected component.
    
    Computing a set with these properties requires some care, and we need to introduce some notation. We fix a vertex v_0, and for each r∈ we  denote by U_r the edge set of the induced graph G[{v∈ V(G)| d_G(v,v_0)≤ r}]. We let L_r be the set of vertices in G∖ U_r that are incident to some edge from U_r. Observe that we can compute U_r and L_r from r and the other input parameters, as the graph G is highly computable.    
    
    We now define r_0 as the smallest natural number such that both E and W are contained in U_r_0. Observe that r_0 exists, and that U_r_0 lies in G. It is straightforward how to compute r_0. Next, we define r_1 as the smallest natural number having the following property: for every pair of vertices u,v∈ L_r_0 that lie in the same infinite connected component of G∖ U_r_0, there is a path from u to v contained in G[U_r_1∖ U_r_0]. 

    The number r_1 is well defined, and can be computed from the inputs. We provide the details for the interested reader. Observe that for every pair of vertices u and v in L_r_0 that lie in the same infinite connected component of G∖ U_r_0, there is a path from u to v in G∖ U_r_0, since such graph is connected. Moreover, this path is contained in G[U_r∖ U_r_0] for some r big enough. As there are finitely many paths to consider, it follows that r_1 exists. In order to compute r_1 it suffices to show that the defining condition for r_1 is decidable given an arbitrary number r≥ r_0. For this we need the algorithm 𝒜. In order to check whether r≥ r_0 satisfies the condition, we first use the algorithm 𝒜 to list all pairs of vertices in L_r_0 that lie in the same infinite connected component from G∖ U_r_0. Then, for each pair of vertices of this list, we check whether they lie in the same connected component of the finite graph G[U_r∖ U_r_0]. 

    
    After computing r_1, we  compute the set U_f of all edges in a finite connected component of G∖ U_r_1. It is clear how to do this with the algorithm 𝒜. We define U=U_r_1∪ U_f, and we claim that this set verifies conditions (1), (2), (3) and (4) defined above. Conditions (1), (2) and (4) are clear. We verify condition (3), so let u and v be vertices in L_r_1 as in the definition of condition (3). Observe that there is a path completely contained in  G[U_r_1∖ U_r_0], from the vertex u to some vertex u' in L_r_0. The existence of this path can be seen by taking any path with minimal length from u to v_0. Similarly, there is a path completely contained in  G[U_r_1∖ U_r_0] from the vertex v to some vertex v' in L_r_0. But there is also a path in G[U_r_1∖ U_r_0] from u' and v' (this was the defining condition for r_1). We can use these three paths to obtain a new path in G[U_r_1∖ U_r_0] from u to v, so our claim follows.
    



    
    We are almost ready to count the number of infinite connected components in G∖ E. Let V be the set of all vertices in G∖ U that are incident to some edge from U. We use the algorithm 𝒜 to compute a partition V=V_1⊔…⊔ V_k  as indicated before. Our task now is to understand for which i j, V_i and V_j are in the same connected component of G∖ E. 
    
    We claim that the infinite connected component of G∖ E that contains V_i equals the one that contains V_j if and only if there is a path within G[U] that visits no edge from E, and that joins some vertex in V_i to some vertex in V_j. The backward implication is obvious. For the forward implication, suppose that V_i and V_j lie in the same connected component of G∖ E. Then there is a path p in G whose initial vertex is in V_i, whose final vertex is in V_j, and which visits no edge from E. 
    
    Some segments of p may escape from the graph G[U∖ E] through a vertex in V, and then enter again to G[U∖ E] through another vertex in V. Condition (3) in the definition of U ensures that we can replace these segments by segments completely contained in G[U∖ E]. After replacing all these segments, we end up with a path with the same initial and final vertex as p, but contained in G[U∖ E]. This shows the forward implication. 
    
    Finally, we define an equivalence relation ∼ in {1,…,k} as follows: i∼ j when there is a path in G[U] that visits no edge from E, and that joins some vertex in V_i to some vertex in V_j. This relation is computable because G[U] is a finite graph, and we can compute the number of  equivalence classes of ∼. The paragraph above shows that this number equals _G(E). This finishes our computation. 
 

A direct consequence of this result is that for each graph G there is an algorithm that computes _G(E) for any given E, and thus both G and G are (non-uniformly) decidable sets.  


    If G is a connected highly computable graph with finitely many ends, then the function E↦_G(E) is computable. In particular, G and G are decidable. 


    Let us denote by S(G,E,n,W)=_G(E) the computable function from  <Ref>, where G is a highly computable graph with n ends, E is a finite set of edges and W is some element in G. When seen as a function of E, that is, when G,n,W are fixed, this is a computable function that allows to decide both G and G, as E∈G_G(E)≥2
and E∈G_G(E)=n.



We now show that in the uniform setting and without any extra information, we have that the function (G,E)↦_G(E) is only upper semicomputable. Observe that now there is no assumption on the number of ends of G.


There is an algorithm which given a description for a highly computable graph G and E⋐ E(G), computes a  sequence of natural numbers (_G,n(E))_n∈ whose minimum equals _G(E).



Let G and E be as in the statement. We proceed as in the first part of the proof of <Ref> and let V be the set
of vertices in G∖ E that are incident to some edge
in E. Further, for each v∈ V, we let C_v be the connected
component of G∖ E that contains v. Now, for each vertex v∈ V and each n∈, we define E_v,n
as the set edges in some path in G of length at most n, starting at v, and that visit no edge from E. Observe that these sets can be uniformly computed (from G, E,
v and n).  It is then clear that for all u,v∈ V: 


  * C_v is finite when for some n, we have E_v,n=E_v,n+1.

  * C_u=C_v when for some n, we have E_u,n∩ E_v,n∅. 

For every n∈ we let _G,n(E) be the
number of infinite connected components of G∖ E that
we can distinguish with the collection of sets {E_v,n| v∈ V}
and the observations above. By this we mean the following. 

We let 𝒜 _n={E_v,n| v∈ V,  E_v,n+1 E_v,n}. We define a relation ∼ on A_n by setting E∼ E' E∩ E'∅, and we extend ∼ to its transitive closure. Finally, we let _G,n(E) be the number of equivalence classes of ∼. It is clear that the sequence (_G,n(E))_n∈ converges monotonously to  _G(E), so our claim follows.  



As a corollary we obtain the corresponding upper bound on the complexity of deciding G, uniformly in G. 


The problem of deciding membership
in G with an algorithm uniform on G, is Π_1^0. 
That is, there is an algorithm which, on input a connected and highly
computable graph G and a finite set of edges E, halts if and
only if E∉G. 


In <Ref> we will show that
this problem is in fact Π_1^0-complete in its uniform version. We will also study the difficulty of computing G, from a description of G. 

    All the notions and results of this section can be extended to the case of graphs which are not necessarily locally finite (recall that in this case the vertex degree function is assumed to be computable as a function of  V(G)→∪{∞}, see <Ref>). The intuitive idea is that given E⋐ E(G), the set of vertices in G∖ E incident to edges from E is finite and computable, even if G is not locally finite. We can use this finite set of vertices as labels for the connected components of G∖ E, and reproduce the same computations (see for instance <cit.>). It is not hard then to adapt the proof of <Ref> to this more general case. Observe that given a graph G that is not locally finite, the sets U_r defined in the proof may be infinite. However, it suffices to replace these sets by finite approximations to them; the rest of the argument remains unchanged.

Let us end this section by illustrating an interesting connection between the separation problem and the problem of computing infinite paths in a graph. In particular, we will see that as a consequence of our results, infinite graphs with finitely many ends always admit computable infinite paths. 



 §.§ Computing infinite paths by separation

The word path receives different meanings in graph theory, according to whether one admits repeated vertices or not. We say that a finite or infinite path is  simple when every vertex is visited at most once.
  
A fundamental result in graph theory, known as König's Infinity Lemma,
asserts that a connected and locally finite graph admits an infinite
simple path if and only if it is infinite. It is well known that this result is non effective in general, in the sense that there exists highly computable
graphs satisfying these hypotheses but where all infinite simple paths are uncomputable, see for instance <cit.> and <cit.>.

Here we establish a close connection between the separation problem, and the problem of determining whether a finite simple path in a graph can be extended to an infinite one. Let us denote by G the set of finite words v_0… v_n∈ V(G)^∗ such that v_0,…,v_n is a simple path in G that can be extended to an infinite simple path (v_n)_n∈. Our goal is to prove: 













Let G be a highly computable and connected infinite 
graph. Then G≥_TG. If G is a tree, then
we have an equivalence G≡_TG. The reductions
are uniform on G. 


Putting this result together with <Ref>, we obtain the following amusing consequence. 


     If G is a highly computable infinite graph with finitely many ends, then G is a decidable set. In particular,  G admits computable infinite simple paths. 


In other words, the property of “having infinite simple paths but no computable one" is exclusive to graphs with infinitely many ends. The proof of <Ref> will be based on the following lemma. 


    Let G be a highly computable graph. Then G is Turing equivalent to the set of pairs (E,U) where E∈G and  U is the (finite) subset of vertices that are adjacent to E that belong to an  infinite connected component of G∖ E. 
    Moreover, the reduction is uniform on the graph G. 


We prove the nontrivial reduction. For this we describe an effective procedure which given E∈ and with oracle access to G, computes the set of
vertices U as in the statement.
On input E, we start by computing the set  {u_1,…,u_n} of vertices in ∖ E
which are incident to E. For each i, we let _i be the connected component
of ∖ E containing u_i. In this notation, the set U that we are trying to compute equals  {u_i : G_i is infinite}. For each i∈{1,…,n} and r∈, we define
E_i,r as the set of edges that lie in a path of length at most
r, with initial vertex u_i, and which visits no edge from E.
As  is highly computable, we can compute E_i,r from E,
i and r. Observe now that _i is infinite if and only if for some r, the set of edges E_i,r lies in .
This is a Σ_1^0 condition with oracle access to . But “G_i is finite” is also a  Σ_1^0 condition. It follows that given E we can compute the set {i∈{1,…,n} : G_i is infinite}, which is what we wanted. 








Let v_0… v_n be a word in V(G)^∗. As the graph G is highly computable, we can check whether it corresponds to a finite simple path, that is, whether v_i is adjacent to v_i+1 and whether no vertices are repeated. Let E be the set of all edges incident to some of these v_i. Now observe that (v_i)_i=0^i=n can be extended to an infinite simple path in G if and only if v_n is adjacent to some vertex from G that lies in an infinite connected component from G∖{v_0,…,v_n}=G∖ E. This is decidable with oracle G by <Ref>. This proves the reduction G≥_TG. 

We now assume that  is a tree, and prove the reduction G≥_TG.
We exhibit a procedure which, given a finite set E⊂ E(), a
vertex u in ∖ E that is incident to some edge
in E, and using G as oracle, determines if the connected
component of ∖ E containing u is infinite. It
is clear how to use this information to check whether E∈G. The procedure is as follows. We denote by C be the connected component
of ∖ E containing u. We start by computing the
set V of vertices adjacent to u in the graph ∖ E.
This is possible as the graph is highly computable. If this set is
empty, then we conclude that C is certainly finite. If V is
nonempty, then we observe that, by König's infinity Lemma, C
is infinite if and only if it has some infinite path starting at u. Moreover, these paths are in correspondence
with those infinite paths in  that start at u and then visit
some vertex v∈ V. This is true because both C and  are trees. Thus in order to decide whether
C is infinite, it suffices to check whether some of the finitely
many elements {uv| v∈ V} lies in G. 


The following question raises naturally from <Ref>.

    Is it true that G≡_TG for every locally finite graph G? 


We also mention that it is not clear if  G allows to determine whether a finite path can be extended to a two-way infinite path. It can be proved that for a highly computable infinite tree G we have that 

    {p∈G : p  can be extended to a two-way infinite path}

is Turing equivalent to G, with a reduction uniform on the tree G. This is a straightforward adaptation of the proof for <Ref>. However, it is not clear whether any of these reductions can be adapted to graphs that are not necessarily trees. 

We now provide an example illustrating the limitations of <Ref>. A finite path (v_i)_i=n^i=m in a graph is called geodesic when its length is minimal among all finite paths with the same initial and final vertex, and an infinite path is geodesic when its restriction to {n,…,m} is geodesic for all n,m∈, n<m. These concepts are fundamental in combinatorial and geometric group theory, see for instance <cit.>. 

    There is a highly computable graph Λ with one end, where the degree of every vertex is at most 6, such that all infinite geodesic paths are uncomputable. Moreover, the set 
    {p∈Λ : p  can be extended to an infinite geodesic path}
 is not c.e.


    Let T be a subtree of the rooted binary tree that is connected, highly computable, infinite, and with no computable infinite simple path. The existence of T is proved in <cit.>. We define a new graph Λ as follows. The vertex set of Λ is the cartesian product V(T)× V(T), and two vertices (u_1,v_1) and (u_2,v_2) are neighbors when one of the following conditions occurs:
    
        
  * u_1=u_2 and v_1 is adjacent to v_2 in T.
        
  * v_1=v_2 and u_1 is adjacent to u_2 in T.
    
     It is clear that Λ is highly computable, and that every vertex has degree at most 6. Observe that a path p in Λ can be seen as a combination of two paths in T, p_1 and p_2, that are “visited" by p one node at a time, jumping between p_1 and p_2 from time to time. Importantly, different orders of visiting p_1 and p_2 correspond to different paths in Λ. Moreover, p can be made simple even if the paths p_1 and p_2 are not. In particular, it is not hard to adapt the argument used to show that the grid has one end, to prove that so does Λ. We leave these details to the reader.  

    Let us now examine the distance d_Λ, and geodesics in the graph Λ. We claim that given a pair of vertices (u,v) and (u',v') in Λ, their distance d_Λ satisfies the following:
    d_Λ((u,v),(u',v'))=d_T(u,v)+d_T(u',v').

    This simply follows by examining the definition of Λ, but we review the details for the interested reader. Consider geodesics u=u_0,…,u_n=u' and v=v_0,…,v_m=v' in the graph T. Then (u_i,v_0)_i=0^i=n is a path in Λ from (u_0,v_0) to (u_n,v_0), and (u_n,v_i)_i=0^i=m is a path in Λ from (u_n,v_0) to (u_n,v_m). Thus we can  “paste” them at the vertex (u_n,v_0) to obtain a path with length n+m, whose initial vertex is (u,v) and whose final vertex is (u',v'). This proves the inequality ≤ in <Ref>. For the other inequality, observe that given a path (u,v)=(u_0,v_0),(u_1,v_1),…,(u_k,v_k)=(u',v') in Λ, we can project to the first and second coordinate and recover two paths in T, one from u to u' and another one from v to v'. Indeed, we can partition 
    
    {0,…,k-1}={i:u_i u_i+1}⊔{i:v_i v_i+1}.
 
    The fact that these sets are disjoint follows from the fact that for i< k and u_i u_i+1, we have v_i=v_i+1 by the definition of the edge relation of Λ.
    After reordering, the first set can be used as index set for a path from u to u', while the second can be used as index set for a path from v to v'. This proves the inequality ≥ in <Ref>. 

    Now let (u_n,v_n)_n∈ be a geodesic infinite path in Λ, and suppose that it is computable to reach a contradiction. Thus for each n we have 
    d_Λ((u_0,v_0),(u_n,v_n))=n.
 For n≥ 1 arbitrary, it is not possible to have  d_T(u_0,u_n)<d_T(u_0,u_n+1) and d_T(v_0,v_n)<d_T(v_0,v_n+1), this follows from the definition of the edge relation for Λ. Joining this  fact with <Ref>, we conclude that  (d_T(u_0,u_n))_n∈ and (d_T(v_0,v_n))_n∈ are nondecreasing sequences, and at least one of them tends to infinity. We suppose without loss of generality that (d_T(u_0,u_n))_n∈ tends to infinity. Thus the sequence (u_n)_n∈ may have some repeated elements, but each element can be repeated  only finitely many times, and with a set of indices that is a connected interval of . Thus we can define a new sequence (u'_n)_n∈ by removing all repetitions from (u_n)_n∈. It is clear that this sequence is an infinite simple path in T, and it is computable, contradicting our hypothesis on T.

    Finally, observe that if  the set 
    C={p∈Λ : p  can be extended to an infinite geodesic}
 was c.e. then we could compute an infinite geodesic in a recursive manner. That is, we run an enumeration of C until a first element p_1 is enumerated, then we wait until an element p_2 that extends p_1 appears, and so on. 



Notice that even though the graph Λ above does not have any computable geodesic infinite path, it must have some computable infinite simple path, by <Ref>.  What do such paths look like then? The key observation is that, if we think of a path in Λ as a combination of two paths p_1 and p_2 in the tree T, then one can search for an infinite path in T using p_1 while keeping p_2 at a fixed node, and in case we chose the wrong branch and end up in a leaf of T, we can change the node from p_2 and then “go back" with p_1 to try a different branch, without formally repeating nodes in Λ.  



We finish this section recalling  other known results about decision problems for finite paths on infinite graphs. It is proved in <cit.> that there is a highly computable graph with one end and  which admits infinite Hamiltonian paths, but no computable one. Thus for this graph the problem of determining whether a simple path can be extended to an infinite Hamiltonian path is undecidable. On the other hand, it is proved in <cit.> that this problem becomes decidable when we instead consider 3-paths and Hamiltonian 3-paths, where a sequence of vertices (v_i)_i=0^i=n is a 3-path in a graph G when the distance between consecutive vertices is at most 3. Finally, it is proved in <cit.> that given a highly computable Eulerian graph, the problem of determining whether a path can be extended to an infinite Eulerian path is decidable. 



Let us observe that given a highly computable graph G with finitely many ends, G may have some 
Let G be a highly computable and connected graph with finitely many ends. We have proved that G is a decidable set (  However, it may have interesting subsets with different complexities. For instance, it is proved in <cit.> that the set of paths in that can be extended to a one-way (or two-way) Eulerian path is decidable. In contrast, it is proved in <cit.> that this is false for Hamiltonian paths. The author constructs an example of a graph G with one end which admits one-way infinite Hamiltonian paths, but in such a manner that none of them is computable. An easy argument shows that for this graph, the set 
    {p∈G : p  can be extended to a one-way Hamiltonian path}
 is not even recursively enumerable. More recently, it 

We have proved that if G has finitely many ends then G is a decidable set. However, some subsets of interest may still be undecidable. For instance, it is proved in <cit.> that there is a highly computable graph G with one end which admits infinite Hamiltonian paths, but no computable Hamiltonian path. An easy argument shows that then 
    {v_0… v_n∈G :  v_0… v_ncan be extended to an infinite Hamiltonian path}
 is not even recursively enumerable. Here we provide another example in the same direction. We say that an infinite path (v_n)_n∈ in a graph G is geodesic when for all n,m∈ we have d_G(v_n,v_m)=|m-n|.
Proposition. There is a highly computable graph with one end, and thus the set of infinite paths is computable by our results, but where no geodesic infinite path is computable. 
 
Proof. Let T be a subtree of the infinite binary tree that is highly computable, and that has no computable infinite path [cita]. Then the product graph T× T satisfies the claim. 






§ THE COMPLEXITY OF THE EULERIAN PATH PROBLEM


The celebrated work by Erdős, Grünwald and Vázsonyi <cit.> established necessary and sufficient conditions for a countably infinite graph to admit either a one-way or a two-way Eulerian path. We start this section by recalling this characterization:

 
Let G be a graph. 

    
  * G admits a one-way infinite Eulerian path if and only if it satisfies the following set of conditions, called :
    
        
  * E(G) is countable and infinite.
        
  * G is connected.
        
  * Either G has exactly one vertex with odd degree, or G has at least one vertex with infinite degree and no vertex with odd degree.   
        
  * G has one end.
    
    
  * G admits a two-way infinite Eulerian path if and only if it satisfies the following set of conditions, called :
    
        
  * E(G) is countable and infinite.
        
  * G is connected.
        
  * The degree of each vertex is either even or infinite.
        
  * G has one or two ends. 
        
  * If E is a finite set of edges
        which induces a subgraph where all vertices have even degree, then
        G∖ E has one infinite connected component.
    


A proof of this result can also be found on <cit.>. Using the characterization above, it has been proven in <cit.> that deciding if a highly computable graph admits a one-way Eulerian path (i.e. if a graph satisfies the set of conditions ) is Π_2^0-complete. This turns out to be the same difficulty of deciding whether a highly computable graph as exactly one end: therefore, it is natural to ask whether the condition about having one end encapsulates most of the hardness of this question, making this decision task easier if we consider only graphs with the correct number of ends. 

In the rest of this section, we show that, indeed, deciding whether a highly computable graph admits a one-way Eulerian path provided that this graph has one end is only Σ_2^-1-complete. Moreover, to complement the work done in <cit.>, we also consider two-way infinite Eulerian paths and show that deciding their existence for highly computable graphs is, again, Π_2^0-complete in general, but it becomes only Π_1^0-complete knowing that this graph has one end. Finally, we show that, whenever G is a highly computable graph with two ends, then we can decide whether G has a two-way Eulerian path using ∅ ' as an oracle, meaning that, again, the problem becomes strictly simpler than in the general case. In terms of many-one degrees, we show that every Δ_2^0 set can be realized as an index set of the form {e:  G_e admits a two-way Eulerian path }, for a uniformly highly computable sequence (G_e)_e ∈ of graphs with two ends. 

The results of this section will therefore give a complete picture of the hardness of the problem of deciding whether a given highly computable graph is Eulerian (see <Ref>).











 §.§ Computable and highly computable multigraphs

For simplicity and clarity, so far we have proved all our results in the setting of simple graphs, that is, with no loops or multiple edges between vertices allowed. However, when considering Eulerian paths it is natural to allow multigraphs, since for instance the graph with a single vertex and infinitely many loops, admits both a one-way and a two-way infinite Eulerian path. For this reason, in this section we shall consider highly computable multigraphs. Let us then recall that in a multigraph G, the degree of the vertex v equals the number of edges incident to v, where loops are counted twice. A multigraph G=(V,E) is computable when V(G) is a decidable subset of , and we have a computable function E(G) V(G)^2→ such that E(G)(u,v) is the number of edges joining u to v in G. The definitions of highly computable multigraph, and highly computable sequence of multigraphs are a straightforward generalization of the ones for simple graphs.  It is easy to check that all the results proved in the previous section are valid in this more general context, so we will use them without further clarifications.  





 §.§ One-way Eulerian paths

We begin by revisiting the result from <cit.> on the Π_2^0-completeness of deciding whether a highly computable graph admits a one-way Eulerian path. Recall that Eulerian paths can exists only for graphs with one or two ends. Thus, the complexity of this problem is related to the complexity of counting ends, which was shown in <cit.> to also be Π_2^0-complete. Let us start by giving an alternative proof of the latter fact by using a construction that we will employ, with some modifications, several times in what follows. 

 
    Let k∈, k≥ 1. The problem of deciding whether a highly computable graph G has at most k ends is Π_2^0-complete. Moreover, there is a highly computable sequence of graphs (G_e^k)_e ∈ where every G_e^k has either k or k+1 ends and the set {e∈:   G_e  has  k  ends} is Π_2^0-complete.


    Let k∈. We start by observing that the problem of determining whether a highly computable graph G has at most k ends is at most Π_2^0. Indeed, we can write such property as follows:
    
    (∀ E ⋐ E(G))(∃ n∈)(_G,n(E)≤ k)

    
    
    Where _G,n(E), as defined in <Ref>, denotes the number of infinite connected components that we can distinguish by inspecting a ball of radius n. We now prove completeness. We construct a uniformly highly computable sequence of graphs (G_e^1)_e ∈ with either one or two ends, such that {e | G_e^1  has one end } is Π_2-complete.

    Let us fix a computable enumeration (W_e)_e ∈ of c.e. sets. Recall that Inf= {e | |W_e|= ∞} is a Π_2^0-complete set (and is complement Fin is Σ_2^0-complete): hence, our goal is to construct (G_e^1)_e ∈ in such a way that {e | G_e^1  has one end }≡_m Inf. With these elements at hand, we define a total computable function f: ^2 →  by recursion. We set f(e,0)=0, and then
    
    f(e,s) = 
            1 - f(e,s-1),     if W_e,s W_e,s-1
    
            f(e,s-1) ,     otherwise.

    It is clear that f(e,  · ) is eventually constant if and only if e ∉Inf. Now, for each e ∈, we define G_e by letting V(G_e^1) = and 
    E(G_e^1) = {(s,s+1) | s ∈}∪{(-s-1,-s) | f(e,s) = f(e,s-1) }

    ∪{(-s,s), (-s-1,s) | f(e,s)  f(e,s-1) }.

    
    
    Now that we have defined the family (G^1_e)_e∈, we verify that {e | G_e^1  has one end } is equal to the Π_2-complete set Inf. Let us describe how to draw the graph G^1_e for fixed e. We compute f(e,s) for each s and in increasing order. As long as f(e,s)=f(e,s-1), we put edges between consecutive integers in {-s-1,…,s+1}, so the graph looks like a line:

    
        

            
                at (-1,0) (-1) ∙;
                at (0,0) (0) ∙;
                at (1,0) (1) ∙;
                at (-4,0) (-s) ∙;
                at (4,0) (s) ∙;
                at (-5,0) (-s-1) ∙;
                at (5,0) (s+1) ∙;
                at (-1,0.3) -1;
                at (0,0.3) 0;
                at (1,0.3) 1;
                at (-4,0.3) -s;
                at (4,0.3) s;
                at (-5,0.3) -s-1;
                at (5,0.3)  s+1;
                (-1) – (0);
                (0) – (1);
                (-1) – (-2,0);
                [dashed] (-2.1,0) – (-2.9,0);
                (-3,0) – (-s);
                (1) – (2,0);
                [dashed] (2.1,0) – (2.9,0);
                (3,0) – (s);
                [blue, thick] (-s) – (-s-1);
                [blue, thick] (s) – (s+1);
                [dashed] (-s-1) – (-6,0);
                [dashed] (s+1) – (6,0);
            
        

    
            
    But, as soon as we see that f(e,s)  f(e,s-1), we omit the edge between -s and -s-1 and, instead, connect s to -s and also to both s+1 and -s-1.

    
        

            
                at (-1,0) (-1) ∙;
                at (0,0) (0) ∙;
                at (1,0) (1) ∙;
                at (-4,0) (-s) ∙;
                at (4,0) (s) ∙;
                at (-5,0) (-s-1) ∙;
                at (5,0) (s+1) ∙;
                at (-1,0.3) -1;
                at (0,0.3) 0;
                at (1,0.3) 1;
                at (-4,0.3) -s;
                at (4,0.3) s;
                at (-5,0.3) -s-1;
                at (5,0.3)  s+1;
                (-1) – (0);
                (0) – (1);
                (-1) – (-2,0);
                [dashed] (-2.1,0) – (-2.9,0);
                (-3,0) – (-s);
                (1) – (2,0);
                [dashed] (2.1,0) – (2.9,0);
                (3,0) – (s);
                [blue, thick] (s) – (s+1);
                [blue, thick] (-s) .. controls (-3,-1) and (3,-1) .. (s);
                [blue, thick] (-s-1) .. controls (-2.7,-2) and (2.7,-2) .. (s);
                [dashed] (-s-1) – (-6,0);
                [dashed] (s+1) – (6,0);
            
        

        
            
    Observe that in this manner, we create a cycle graph with vertex set {-s,…,s}. This process is iterated, and more cycles will be created according to the values of f(e,·).
    

    
        

               
                at (0,0) (s) ∙;
                [below = 0 cm of s] s;
                (-2,0) – (s);
                (2,0) – (s);
                [dashed] (-2.1,0) – (-2.6,0);
                [dashed] (2.1,0) – (2.6,0);
                (s) .. controls (-1, 1) and (1, 1) .. (s);
            
        

    
    By definition of f, we have that exactly one cycle is created for each element |W_e|.   
            
                
        
               
            
                at (0,0) (0) ∙;
                at (1,0) (s0) ∙;
                at (2,0) (sk) ∙;
                at (3,0) (s*) ∙;
                (0) .. controls (0.25, 0.5) and (0.75, 0.5) .. (s0);
                (0) .. controls (0.25, -0.5) and (0.75, -0.5) .. (s0);
                [dashed] (s0) – (sk);
                (sk) .. controls (2.25, 0.5) and (2.75, 0.5) .. (s*);
                (sk) .. controls (2.25, -0.5) and (2.75, -0.5) .. (s*);
                (s*) – ++(20:0.75cm);
                [dashed] (s*)++(20:0.75cm) – ++(20:0.75cm);
                (s*) – ++(-20:0.75cm);
                [dashed] (s*)++(-20:0.75cm) – ++(-20:0.75cm);
                [below = 0 cm of 0] 0;
                [below = 0 cm of s0] s_0;
                [below = 0 cm of sk] s_k;
                [below = 0 cm of s*] s^*;
                (U) at ((s*)+(20:1.5cm));
                (B) at ((s*)+(-20:1.5cm));
                (F) at (0.5*(U)+0.5*(B)) ;
                (L) at (0.5*(0)+0.5*(F)) ;
                [below = 0.75cm of L] G_e^1 for e ∈Fin;
            
                            
                at (0,0) (0) ∙;
                at (1,0) (s0) ∙;
                at (2,0) (s1) ∙;
                at (3,0) (s2) ∙;
                (0) .. controls (0.25, 0.5) and (0.75, 0.5) .. (s0);
                (0) .. controls (0.25, -0.5) and (0.75, -0.5) .. (s0);
                (s0) .. controls (1.25, 0.5) and (1.75, 0.5) .. (s1);
                (s0) .. controls (1.25, -0.5) and (1.75, -0.5) .. (s1);
                (s1) .. controls (2.25, 0.5) and (2.75, 0.5) .. (s2);
                (s1) .. controls (2.25, -0.5) and (2.75, -0.5) .. (s2);
                [dashed] (s2) – (4,0);
                [below = 0 cm of 0] 0;
                [below = 0 cm of s0] s_0;
                [below = 0 cm of s1] s_1;
                [below = 0 cm of s2] s_2;
                [below = 0.65 cm of s1] G_e^1 for e ∈Inf; 
            
        

        

    If e ∈Fin, then there is a step s^* after which no new element enters W_e,  meaning that f(e, s)=f(e,s^*) for all s ≥ s*. In this case, G_e^1 has two ends, as G_e^1 ∖{v | |v| < s^* } is isomorphic to (, {(x,x+1) | x ∈}) via 
    x ↦
            x + s^*,     if x≥ 0 
    
            x - s^*,     otherwise.


    On the other hand, if e ∈Inf, G_e^1 has one end.  Indeed, for any E ⋐ E(G_k^1), we can consider n= max{|v| | v  is adjacent to some edge in E }: since E is contained in the set of edges of G_k^1[{s | |s| ≤ n} ], it is enough to observe that, by construction, G_e^1 ∖{s | |s| ≤ n} = G_e^1[{s | |s| > n} ] is an infinite connected graph. 

    Thus, we have proved that the family of graphs (G^1_e)_e∈ has the desired properties. The claim for k > 1 follows easily by considering the highly computable sequence of graphs (G_e^k)_e ∈ defined by attaching k-1 copies of the graph (∖{0}, {(s,s+1) | s ∈∖{0}}) to the vertex 0 of each G_e^1 defined above. Namely, we consider graphs which look as follows.

    
        

           
                at (0,0) (0) ∙;
                at (1,0) (s0) ∙;
                at (2,0) (sk) ∙;
                at (3,0) (s*) ∙;
                (0) .. controls (0.25, 0.5) and (0.75, 0.5) .. (s0);
                (0) .. controls (0.25, -0.5) and (0.75, -0.5) .. (s0);
                [dashed] (s0) – (sk);
                (sk) .. controls (2.25, 0.5) and (2.75, 0.5) .. (s*);
                (sk) .. controls (2.25, -0.5) and (2.75, -0.5) .. (s*);
                (s*) – ++(20:0.75cm);
                [dashed] (s*)++(20:0.75cm) – ++(20:0.75cm);
                (s*) – ++(-20:0.75cm);
                [dashed] (s*)++(-20:0.75cm) – ++(-20:0.75cm);
                [below = 0 cm of 0] 0;
                [below = 0 cm of s0] s_0;
                [below = 0 cm of sk] s_k;
                [below = 0 cm of s*] s^*;
                (U) at ((s*)+(20:1.5cm));
                (B) at ((s*)+(-20:1.5cm));
                (F) at (0.5*(U)+0.5*(B)) ;
                (U') at ((0)+(160:1.5cm));
                (B') at ((0)+(-160:1.5cm));
                (F') at (0.5*(U')+0.5*(B')) ;
                (L) at (0.5*(F')+0.5*(F)) ;
                (0) – ++(160:0.75cm);
                [dashed] (0)++(160:0.75cm) – ++(160:0.75cm);
                (0) – ++(-160:0.75cm);
                [dashed] (0)++(-160:0.75cm) – ++(-160:0.75cm);
                (T) at ((0)+(158:1.5cm));
                (B) at ((0)+(-158:1.5cm));
                [decorate,decoration=brace,amplitude=5pt,mirror,raise=1ex] (T) – (B);
                (C) at (0.5*(T)+0.5*(B)) ;
                [rotate=90] at ((C)+(0.3,0.025)) …;
                [above = 0.5 cm of C] (label) (∖{ 0 })^k;
                [->] (C)++(-0.5,0.1) to[bend left] (label);
                [below = 0.75cm of L] G_e^k for e ∈Fin;
            
            
                at (0,0) (0) ∙;
                at (1,0) (s0) ∙;
                at (2,0) (s1) ∙;
                at (3,0) (s2) ∙;
                (0) .. controls (0.25, 0.5) and (0.75, 0.5) .. (s0);
                (0) .. controls (0.25, -0.5) and (0.75, -0.5) .. (s0);
                (s0) .. controls (1.25, 0.5) and (1.75, 0.5) .. (s1);
                (s0) .. controls (1.25, -0.5) and (1.75, -0.5) .. (s1);
                (s1) .. controls (2.25, 0.5) and (2.75, 0.5) .. (s2);
                (s1) .. controls (2.25, -0.5) and (2.75, -0.5) .. (s2);
                [dashed] (s2) – (4,0);
                [below = 0 cm of 0] 0;
                [below = 0 cm of s0] s_0;
                [below = 0 cm of s1] s_1;
                [below = 0 cm of s2] s_2;
                (0) – ++(160:0.75cm);
                [dashed] (0)++(160:0.75cm) – ++(160:0.75cm);
                (0) – ++(-160:0.75cm);
                [dashed] (0)++(-160:0.75cm) – ++(-160:0.75cm);
                (T) at ((0)+(158:1.5cm));
                (B) at ((0)+(-158:1.5cm));
                [decorate,decoration=brace,amplitude=5pt,mirror,raise=1ex] (T) – (B);
                (C) at (0.5*(T)+0.5*(B)) ;
                [rotate=90] at ((C)+(0.3,0.025)) …;
                
                
                [above = 0.5 cm of C] (label) (∖{ 0 })^k;
                [->] (C)++(-0.5,0.1) to[bend left] (label);
                (U') at ((0)+(160:1.5cm));
                (B') at ((0)+(-160:1.5cm));
                (F') at (0.5*(U')+0.5*(B')) ;
                (L) at (0.5*(F')+(2,0)) ;
                [below = 0.75cm of L] G_e^k for e ∈Inf;
              
            
        

    

    

    It is clear that G_e^k has k ends if G_e has one end, while it has k+1 ends if G_e has two ends.


Using the construction developed in the proof above, we can also give an alternative proof of the Π_2^0-completness of deciding existence of one-way Eulerian paths. 

 
    The problem of deciding whether a highly computable graph admits a a one-way Eulerian path is Π_2^0-complete. 


    Since we consider only countable, connected and locally finite graphs, the set of conditions  in our case reduces to the following condition:
    
    G  has exactly one vertex of odd degree and has one end.

    The statement G has exactly one vertex of odd degree is a conjunction of a Σ_1^0 statement and a Π_1^0 statement, which makes it Σ_2^-1.  It follows from <Ref> that the property of having one end is Π_2^0. Hence, <Ref> is a Π_2^0 property.

    Now we show Π_2^0-completeness. To do so, it is enough to slightly modify the construction in the proof of <Ref>. Indeed, we define the highly computable sequence of multigraphs (G_e)_e ∈ by letting V(G_e) = and 
    
    E(G_e)(n,m) = 
            2,    if n > m ≥ 0  and n=m+1 
    
            1,    if 0 ≤ m < n  and n=m+1  and f(e,s) = f(e,s-1) 
    
            1,    if (n=-m  or (n > m  and m=-n-1)) and f(e,s)  f(e,s-1) 
    
            0,    otherwise.


    In other words, we perform the same algorithm that we used to construct the sequence in <Ref>, with the only difference that now each vertex with non-negative index is joined to its successor by two edges. Thus, at any stage s where f(e,s) = f(e,s-1), we add edges as shown in the picture below.
    
        

            
                at (-1,0) (-1) ∙;
                at (0,0) (0) ∙;
                at (1,0) (1) ∙;
                at (-4,0) (-s) ∙;
                at (4,0) (s) ∙;
                at (-5,0) (-s-1) ∙;
                at (5,0) (s+1) ∙;
                [above = 0cm of -1] -1;
                [above = 0cm of 0] 0;
                [above = 0cm of 1] 1;
                [above = 0cm of -s] -s;
                [above = 0cm of s] s;
                [above = 0cm of -s-1] -s-1;
                [above = 0cm of s+1] s+1;
                (-1) – (0);
                (0) .. controls (0.25, 0.5) and (0.75,0.5) .. (1);
                (0) .. controls (0.25, -0.5) and (0.75,-0.5) .. (1);
                (-1) – (-2,0);
                [dashed] (-2.1,0) – (-2.9,0);
                (-3,0) – (-s);
                (1) .. controls (1.25, 0.5) and (1.75,0.5) .. (1.9,0.2);
                (1) .. controls (1.25, -0.5) and (1.75,-0.5) .. (1.9,-0.2);
                [dashed] (2.1,0) – (2.9,0);
                (3.1,0.2) .. controls (3.25,0.5) and (3.75,0.5) .. (s);
                (3.1,-0.2) .. controls (3.25,-0.5) and (3.75,-0.5) .. (s);
                [blue, thick] (-s) – (-s-1);
                [blue, thick] (s) .. controls (4.25, 0.5) and (4.75,0.5) .. (s+1);
                [blue, thick] (s) .. controls (4.25, -0.5) and (4.75,-0.5) .. (s+1);
                [dashed] (-s-1) – (-6,0);
                [dashed] (s+1) – (6,0);
            
        

    

    On the other hand, whenever f(e,s)  f(e,s-1), the situation will look as in the following picture.
    
        

            
                at (-1,0) (-1) ∙;
                at (0,0) (0) ∙;
                at (1,0) (1) ∙;
                at (-4,0) (-s) ∙;
                at (4,0) (s) ∙;
                at (-5,0) (-s-1) ∙;
                at (5,0) (s+1) ∙;
                [above = 0cm of -1] -1;
                [above = 0cm of 0] 0;
                [above = 0cm of 1] 1;
                [above = 0cm of -s] -s;
                [above = 0cm of s] s;
                [above = 0cm of -s-1] -s-1;
                [above = 0cm of s+1] s+1;
                (-1) – (0);
                (0) .. controls (0.25, 0.5) and (0.75,0.5) .. (1);
                (0) .. controls (0.25, -0.5) and (0.75,-0.5) .. (1);
                (-1) – (-2,0);
                [dashed] (-2.1,0) – (-2.9,0);
                (-3,0) – (-s);
                (1) – (2,0);
                [dashed] (2.1,0) – (2.9,0);
                (3.1,0.2) .. controls (3.25,0.5) and (3.75,0.5) .. (s);
                (3.1,-0.2) .. controls (3.25,-0.5) and (3.75,-0.5) .. (s);
                [blue, thick] (s) .. controls (4.25, 0.5) and (4.75,0.5) .. (s+1);
                [blue, thick] (s) .. controls (4.25, -0.5) and (4.75,-0.5) .. (s+1);
                [blue, thick] (-s) .. controls (-3,-2) and (3,-2) .. (s);
                [blue, thick] (-s-1) .. controls (-2.7,-2.5) and (2.7,-2.5) .. (s);
                [dashed] (-s-1) – (-6,0);
                [dashed] (s+1) – (6,0);
            
        

    
    
    Therefore, G_e for e ∈Fin will look like this:
    
        

            
                at (0,0) (0) ∙;
                [below = 0 cm of 0] 0;
                at (1,0) (1) ∙;
                [below = 0 cm of 1] 1;
                (0) .. controls (0.25, 0.5) and (0.75,0.5) .. (1);
                (0) .. controls (0.25, -0.5) and (0.75,-0.5) .. (1);
                [dashed] (1) – (1.8,0);
                at (2,0) (2) ∙;
                at (3,0) (3) ∙;
                [below = 0 cm of 3] s_0;
                (2) .. controls (2.25, 0.5) and (2.75,0.5) .. (3);
                (2) .. controls (2.25, -0.5) and (2.75,-0.5) .. (3);
                at (0.5,0.75) (a) ∙;
                [above = 0 cm of a] -1;
                (0) to[bend left] (a);      
                at (2.5,.75) (b) ∙;
                [above = 0 cm of b] -s_0;
                (b) to[bend left] (3);
                (a) – (1,.75);
                [dashed] (1.2,.75) – (1.8,.75);
                (2,.75) – (b);

                at (4,0) (4) ∙;
                
                at (5,0) (5) ∙;
                
                (4) .. controls (4.25, 0.5) and (4.75,0.5) .. (5);
                (4) .. controls (4.25, -0.5) and (4.75,-0.5) .. (5);
                [dashed] (5) – (5.8,0);
                at (6,0) (6) ∙;
                at (7,0) (7) ∙;
                [below = 0 cm of 7] s^*;
                (6) .. controls (6.25, 0.5) and (6.75,0.5) .. (7);
                (6) .. controls (6.25, -0.5) and (6.75,-0.5) .. (7);
                at (4.5,0.75) (c) ∙;
                
                (4) to[bend left] (c);      
                at (6.5,.75) (d) ∙;
                [above = 0 cm of d] -s^*;
                (d) to[bend left] (7);
                (c) – (5,.75);
                [dashed] (5.2,.75) – (5.8,.75);
                (6,.75) – (d);

                [dashed] (3) – (4);

                at (8,.5) (e) ∙;
                at (8,-.5) (e') ∙;

                (7) – (e);
                (7) to[bend left] (e');
                (7) to[bend right] (e');
                [dashed] (e) – (8.7,.9);
                [dashed] (e') – (8.7,-.9);

            
        

    
    
    While G_e for e ∈Inf will be as follows:

    
        

            

                at (0,0) (0) ∙;
                [below = 0 cm of 0] 0;
                at (1,0) (1) ∙;
                [below = 0 cm of 1] 1;
                [<-, red] (0) .. controls (0.25, 0.5) and (0.75,0.5) .. (1);
                [->, blue] (0) .. controls (0.25, -0.5) and (0.75,-0.5) .. (1);
                [dashed] (1) – (1.8,0);
                at (2,0) (2) ∙;
                at (3,0) (3) ∙;
                [below = 0 cm of 3] s_0;
                [<-, red] (2) .. controls (2.25, 0.5) and (2.75,0.5) .. (3);
                [->, blue] (2) .. controls (2.25, -0.5) and (2.75,-0.5) .. (3);
                at (0.5,0.75) (a) ∙;
                [above = 0 cm of a] -1;
                [->] (0) to[bend left] (a);      
                at (2.5,.75) (b) ∙;
                [above = 0 cm of b] -s_0;
                [->] (b) to[bend left] (3);
                (a) – (1,.75);
                [dashed] (1.2,.75) – (1.8,.75);
                (2,.75) – (b);

                at (4,0) (4) ∙;
                
                at (5,0) (5) ∙;
                
                [<-, red] (4) .. controls (4.25, 0.5) and (4.75,0.5) .. (5);
                [->, blue] (4) .. controls (4.25, -0.5) and (4.75,-0.5) .. (5);
                [dashed] (5) – (5.8,0);
                at (6,0) (6) ∙;
                at (7,0) (7) ∙;
                [below = 0 cm of 7] s_k;
                [<-, red] (6) .. controls (6.25, 0.5) and (6.75,0.5) .. (7);
                [->, blue] (6) .. controls (6.25, -0.5) and (6.75,-0.5) .. (7);
                at (4.5,0.75) (c) ∙;
                
                [->] (4) to[bend left] (c);      
                at (6.5,.75) (d) ∙;
                [above = 0 cm of d] -s_k;
                [->] (d) to[bend left] (7);
                (c) – (5,.75);
                [dashed] (5.2,.75) – (5.8,.75);
                (6,.75) – (d);

                [dashed] (3) – (4);

                [dashed] (7) – (7.8,0);

            
        

    
 

    Observe that, for every e, the only vertex with odd degree in G_e is 0: then G_e admits an infinite Eulerian path if and only if G_e has one end. An example of such path is shown in the picture above: this path starts at the vertex 0, reaches vertex s_0 using, say, the blue edges, proceeds backwards through the red edges and then changes direction again passing through the black edges, and so on. By the same reasoning used in the proof of <Ref>, this happens if and only e ∈Inf.


It should be noticed that the proof in <cit.> relies on the construction of  automatic graphs, and hence the above statement actually holds already in the case of automatic graphs. In the next result we show that the problem becomes simpler, in fact, Σ_2^-1-complete, when restricted to graphs with one end. 

 
The problem of deciding whether a highly computable graph with one end admits a a one-way Eulerian path is Σ_2^-1-complete.   


    We already observed that the the statement G has exactly one vertex of odd degree is Δ_2^0: in particular, this statement is a conjunction of a Σ_1^0 statement and a Π_1^0 statement, which makes it Σ_2^-1. It follows that the problem of deciding that a graph satisfies , provided it has one end and it is connected, is at most Σ_2^-1. We now prove completeness. 
    
    Let W be a Σ_2^-1-complete set (the existence of such set as been proved in <cit.>) and f: ^2 → be a computable approximation of W: since W is 2-c.e., we can assume that f changes mind on each element at most twice. Moreover, we can assume that f(e,0)=0 for every e. 

    For every e, we define G_e as follows. Let V(G_e) = and 

    
    E(G_e)(n,m) = 
            2,    if n=s,  m=s+1  and f(e,s)=0 
    
            1,    if  n=s,  m=s+1  and f(e,s)=1 
    
            0,    otherwise.


    Again, we explain how one can define the edge set of E(G_e) in stages. At every stage s, we look at the value of f(e,s). 

    While f(e,s)=0, we keep adding 2 edges between s and s+1. 

    
        

            
                at (0,0) (0) ∙;
                [below = 0 cm of 0] 0;
                at (1,0) (1) ∙;
                [below = 0 cm of 1] 1;
                (0) .. controls (0.25, 0.5) and (0.75,0.5) .. (1);
                (0) .. controls (0.25, -0.5) and (0.75,-0.5) .. (1);
                [dashed] (1) – (1.8,0);
                at (2,0) (2) ∙;
                [below = 0 cm of 2] s;
                at (3,0) (3) ∙;
                [below = 0 cm of 3] s+1;
                [thick, blue] (2) .. controls (2.25, 0.5) and (2.75,0.5) .. (3);
                [thick, blue] (2) .. controls (2.25, -0.5) and (2.75,-0.5) .. (3);
                [dashed] (3) – (3.8,0);
            
        

    

    But whenever f(e,s)=1, we instead start adding only one edge between s and s+1. 

    
        

            
                at (0,0) (0) ∙;
                [below = 0 cm of 0] 0;
                at (1,0) (1) ∙;
                [below = 0 cm of 1] 1;
                (0) .. controls (0.25, 0.5) and (0.75,0.5) .. (1);
                (0) .. controls (0.25, -0.5) and (0.75,-0.5) .. (1);
                [dashed] (1) – (1.8,0);
                at (2,0) (2) ∙;
                at (3,0) (3) ∙;
                (2) .. controls (2.25, 0.5) and (2.75,0.5) .. (3);
                (2) .. controls (2.25, -0.5) and (2.75,-0.5) .. (3);
                at (4,0) (4) ∙;
                [below = 0 cm of 3] s;
                [below = 0 cm of 4] s+1;
                [thick, blue] (3) – (4);
                [dashed] (4) – (4.8,0);
            
        

    

    Finally, it might also happen that f changes its mind again at stage s: hence, we go back to adding  2 edges between s and s+1.
    
    
        

            
                at (0,0) (0) ∙;
                [below = 0 cm of 0] 0;
                at (1,0) (1) ∙;
                [below = 0 cm of 1] 1;
                (0) .. controls (0.25, 0.5) and (0.75,0.5) .. (1);
                (0) .. controls (0.25, -0.5) and (0.75,-0.5) .. (1);
                [dashed] (1) – (1.8,0);
                at (2,0) (2) ∙;
                at (3,0) (3) ∙;
                (2) .. controls (2.25, 0.5) and (2.75,0.5) .. (3);
                (2) .. controls (2.25, -0.5) and (2.75,-0.5) .. (3);
                at (4,0) (4) ∙;
                (3) – (4);
                [dashed] (4) – (4.8,0);
                at (5,0) (5) ∙;
                at (6,0) (6) ∙;
                [below = 0 cm of 6] s;
                (5) – (6);
                at (7,0) (7) ∙;
                [below = 0 cm of 7] s+1;
                [thick, blue] (6) .. controls (6.25, 0.5) and (6.75,0.5) .. (7);
                [thick, blue] (6) .. controls (6.25, -0.5) and (6.75,-0.5) .. (7);
                [dashed] (7) – (7.8,0);
            
        

    
    
    Notice that all G_e's constructed in this way have one end.
    
    Moreover, if f never changes its mind on e, then all vertices in G_e have even degree, hence G_e cannot have a one-way infinite Eulerian path. On the other hand, if f changes its mind on e at step s and never changes its mind again, we have that s has odd degree, while all other vertices have even degree. In this case, which is exactly when e ∈ W, G_e admits a one-way infinite Eulerian path. For example, we have the path described in the picture below: such a path starts at the vertex pointed by the double arrow, crosses our graph backwards going through the red edges until it reaches the vertex 0 and then proceeds forever visiting each black edge in order.

    
        


            
                at (0,0) (0) ∙;
                at (1,0) (1) ∙;
                [->] (0) .. controls (0.25, 0.5) and (0.75,0.5) .. (1);
                [<-, red] (0) .. controls (0.25, -0.5) and (0.75,-0.5) .. (1);
                [dashed] (1) – (1.8,0);
                at (2,0) (2) ∙;
                at (3,0) (3) ∙;
                [->] (2) .. controls (2.25, 0.5) and (2.75,0.5) .. (3);
                [<-, red] (2) .. controls (2.25, -0.5) and (2.75,-0.5) .. (3);
                at (4,0) (4) ∙;
                [->] (3) – (4);
                at (5,0) (5) ∙;
                [->] (4) – (5);
                [dashed] (5) – (5.8,0);
                [->>] (3,-.5) – (3);
            
        

    
    
    Finally, if f changes its mind twice on e, say at stages s and s', both vertices s and s' have odd degree: hence G_e does not admit Eulerian paths.




 §.§ Two-way Eulerian paths

We begin by observing that <Ref> is also valid for two-way Eulerian paths. 
 
    The problem of deciding whether a highly computable graph admits a a two-way Eulerian path is Π_2^0-complete.
    


    Since we consider only countable, connected and locally finite graphs, the set of conditions  reduce to the following:
    
    
        
  * (∀ v ∈ V(G))   (_G(v)  is even)
        
  * G  has at most two ends
        
  * (∀ E ⋐ E(G))(∃ n∈)   ((∃ v ∈ G[E])  _G[E](v) is odd)  (_G,n(E)≤ 1).
    
    Condition (3) is clearly a Π_1^0 statement. By <Ref>, condition (4) is Π_2^0. Let us recall that E→_G,n(E)  was defined in  <Ref>, where we also proved that this function is computable. This fact shows that condition (5) is also Π_2^0. Thus, overall, the complexity of  is at most Π_2^0.

    To prove completeness, it is enough to slightly modify the sequence of graphs (G_e^1)_e ∈ constructed in the proof of <Ref>. Namely, for each e we define H_e as the graph obtained by duplicating each edge in G_e^1. We hence obtain a uniformly highly computable sequence of multigraphs (H_e)_e ∈ where each H_e has either one or two ends and where each vertex has even degree. We claim that 
    
    {e:   H_e  admits a two-way Eulerian path} = {e:   H_e  has one end}.

    Notice that this is enough to conclude the proof, as the set on the right-hand side is Π_2^0-complete by <Ref>.

    Let us first consider the case where H_e has one end. As every vertex in H_e has even degree, it follows that it verifies , so it admits a two-way infinite Eulerian path. For concreteness, let us describe how to obtain such a path. For this we let s_0=0, and denote by s_k the k-th step in which a new element is enumerated into W_e. As we are in the case where W_e is infinite, we have a well-defined infinite sequence (s_k)_k ∈. Then each subgraph H_e[{v∈ V(H_e):   s_k ≤ |v| ≤ s_k+1}∖{-s_k} is even and connected, so by Euler's theorem admits an Eulerian cycle. We can split such a cycle into two disjoint paths from s_k to s_k+1, shown in blue and in red in the picture below. These paths can be joined to construct the desired two-way Eulerian path.
    
        

            
                at (0,0) (0) ∙;
                at (45:1cm) (1) ∙;
                at (-45:1cm) (-1) ∙;
                at ((1)+(1,0)) (2) ∙;
                at ((-1)+(1,0)) (-2) ∙;
                at ((2)+(1,0)) (3) ∙;
                at ((-2)+(1,0)) (-3) ∙;
                at ((3)+(1,0)) (4) ∙;
                at ((-3)+(1,0)) (-4) ∙;
                at ((4)+(-45:1cm)) (5) ∙;
                [red, thick, ->] (0) to[bend left] (1);
                [red, thick, ->] (1) to[bend left] (2);
                [dashed] (2) – (3);
                [red, thick, ->] (3) to[bend left] (4);
                [red, thick, ->] (4) to[bend left] (5);
                [blue, thick, ->] (0) to[bend right] (1);
                [blue, thick, ->] (1) to[bend right] (2);
                [blue, thick, ->] (3) to[bend right] (4);
                [blue, thick, ->] (4) to[bend right] (5);
                [blue, thick, ->] (0) to[bend right] (-1);
                [blue, thick, ->] (-1) to[bend right] (-2);
                [dashed] (-2) – (-3);
                [blue, thick, ->] (-3) to[bend right] (-4);
                [blue, thick, ->] (-4) to[bend right] (5);
                [blue, thick, <-] (0) to[bend left] (-1);
                [blue, thick, <-] (-1) to[bend left] (-2);
                [blue, thick, <-] (-3) to[bend left] (-4);
                [blue, thick, <-] (-4) to[bend left] (5);
                [above left = -0.3 cm of 0] s_k;
                [above left = -0.3 cm of 1] s_k+1;
                [below left = -0.3 cm of -1] -(s_k+1);
                [above right = -0.3 cm of 4] s_k+1-1;
                [below right = -0.3 cm of -4] -s_k+1;
                [above right = -0.3 cm of 5] s_k+1;
                
                
            

             
                
                
                at ((5)+(3,0)) (0') ∙;
                at ((0')+(1,0)) (1') ∙;
                
                [red, thick, ->] (0') .. controls ((0')+(0.25, 0.5)) and ((0')+(0.75,0.5)) .. (1');
                [blue, thick, ->] (0') to[bend left] (1');
                [blue, thick, <-] (0') to[bend right] (1');
                [blue, thick, ->] (0') .. controls ((0')+(0.25,-0.5)) and ((0')+(0.75,-0.5)) .. (1');
                
                
                at ((1')+(1,0)) (2') ∙;
                
                [red, thick, ->] (1') .. controls ((1')+(0.25, 0.5)) and ((1')+(0.75,0.5)) .. (2');
                [blue, thick, ->] (1') to[bend left] (2');
                [blue, thick, <-] (1') to[bend right] (2');
                [blue, thick, ->] (1') .. controls ((1')+(0.25,-0.5)) and ((1')+(0.75,-0.5)) .. (2');
                
                
                [dashed] (2') – ++(0:0.75cm);
                [above = 0 cm of 0'] 0;
                [above = 0 cm of 1'] s_1;
                [above = 0 cm of 2'] s_2;
            
        

    
    On the other hand, if H_e has two ends, then, by construction, W_e is finite. So, there must be a stage s_k in which some element enters W_e for the last time. Let E⋐ E(H_e) be the set whose elements are the two edges joining s_k to s_k+1. Then H_e[E] is an even graph, while H_e∖ E has two infinite connected components, so H_e does not satisfy .


Next, we study the complexity of deciding the existence of a two-way Eulerian path when restricting ourselves only to graphs with, respectively, one or two ends. Let us begin with the case of graphs with one end.
 
    The problem of deciding whether a highly computable graph with one end admits a a two-way Eulerian path is Π_1^0-complete.


    In the case of a highly computable graph with one end, the only condition which is left to check in  is that all vertices in the graph have even degree, which is clearly a Π_1^0 statement. 

    To prove completeness, let us fix a computable enumeration (φ_e)_e ∈ and define the highly computable sequence of multigraphs (G_e)_e ∈ as follows: for every e, we let V(G_e) = and 

    
    E(G_e)(u,v) = 
            2,    if u=s,  v=s+1  and ((φ_e,s↑)  or (φ_e,s-1↓ and φ_e,s↓)) 
    
            1,    if u=s,  v=s+1  and φ_e,s-1↑ and φ_e,s↓
    
            0,    otherwise.


     In other words, we always add two edges between s and s+1, unless φ_e halts in exactly s steps, in which case we only add one edge. Thus, we have the following two cases:

    
        

        


            
                at (0,0) (0) ∙;
                at (1,0) (1) ∙;
                [red, thick, ->] (0) .. controls (0.25, 0.5) and (0.75,0.5) .. (1);
                [blue, thick, ->] (0) .. controls (0.25, -0.5) and (0.75,-0.5) .. (1);
                at (2,0) (2) ∙;
                [blue, thick, ->] (1) .. controls (1.25, 0.5) and (1.75,0.5) .. (2);
                [red, thick, ->] (1) .. controls (1.25, -0.5) and (1.75,-0.5) .. (2);
                
                [dashed] (2) – (2.8,0);
                at (1.4, -1) G_e for φ_e ↑;
            
                
                at (0,0) (0) ∙;
                at (1,0) (1) ∙;
                (0) .. controls (0.25, 0.5) and (0.75,0.5) .. (1);
                (0) .. controls (0.25, -0.5) and (0.75,-0.5) .. (1);

                 [dashed] (1) – (1.8,0);
                at (2,0) (2) ∙;
                at (3,0) (3) ∙;
                
                (2) .. controls (2.25, 0.5) and (2.75,0.5) .. (3);
                (2) .. controls (2.25, -0.5) and (2.75,-0.5) .. (3);
                at (4,0) (4) ∙;
                (3) – (4);
                at (5,0) (5) ∙;
                (4) .. controls (4.25, 0.5) and (4.75,0.5) .. (5);
                (4) .. controls (4.25, -0.5) and (4.75,-0.5) .. (5);
                [below = 0 cm of 3] s;


                [dashed] (5) – (5.8,0);
                at (2.9, -1) G_e for φ_e ↓ in s steps;
            
        

      
    It is clear that the vertices s and s+1 in G_e have odd degree if and only if φ_e halts in exactly s steps. It follows that G_e admits a two-way Eulerian path if and only if e ∈.


We conclude by showing that, in the case of graphs with two ends, the existence of a two-way Eulerian path exhausts exactly the m-degrees of Δ_2^0 sets. 
 
    The problem of deciding whether a highly computable graph with two ends admits a a two-way Eulerian path is Δ_2^0. Moreover, for every Δ_2^0 set X⊂ there is a uniformly highly computable family of graphs (G_e) with two ends, such that 
    
    X={e∈| G_e  admits a two-way infinite Eulerian path}.
 


    We start by proving the upper bound. Let (G_e)_e ∈ be a uniformly highly computable family of connected graphs with two ends. We claim that {e∈| G_e  satisfies }≤_T∅'.

    A Turing reduction which decides whether G_e satisfies  using  is the following. We start by verifying that every vertex in G_e has even degree. This is a Π_1^0 condition and, hence, decidable with oracle ∅'. Now our task is to verify that G_e ∖ E has a single infinite connected component, for every set of edges E that induces an even subgraph of G_e. For this purpose we compute a set S∈G_e, which is possible with oracle ∅ ' by <Ref>. Now let φ be the function from <Ref>. By the Recursion Theorem, from the index e we can compute an index e' of a Turing machine which runs φ(G_e,S,2,E) for every finite set of edges E that induces an even subgraph of G_e, and that halts whenever it finds some E such that φ(G_e,S,2,E)≥ 2. Then φ_e' halts if and only if G_e has a finite set of edges E for which G_e ∖ E has more than one infinite connected component, namely if and only if G_e does not satisfy . This proves that, in order to check whether G_e satisfies , it suffices to ask whether e'∈∅'. This concludes the desired Turing reduction.

    Next, we consider any Δ_2^0 set X and describe the construction of a highly computable sequence of graphs (G_e)_e ∈  such that {e:  G_e  admits a two-way Eulerian path }=X. 
    
    Again, our construction will be a variation of the one used in the proof of <Ref>. Let x(e,s) be a computable approximation to the characteristic sequence of X. Without loss of generality, we can assume that x(e,-1)=x(e,0)=0 for every e. Now, for every e, we let V(G_e) =, while the set of edges is defined by the following effective procedure: 

        
  
  
    
    
        
  * We begin by adding two edges between 0, 1 and 0, -1. 
        
  * We keep adding two edges between both s, s+1 and -s, -(s+1) until we see that x(e,s-1)=x(e,s)=0 (that is, our computable approximation believes that e ∉ X).
    
    
        

            
                at (-1,0) (-1) ∙;
                at (0,0) (0) ∙;
                at (1,0) (1) ∙;
                at (-4,0) (-s) ∙;
                at (4,0) (s) ∙;
                at (-5,0) (-s-1) ∙;
                at (5,0) (s+1) ∙;
                [above =0.1cm of -1] -1;
                [above =0.1cm of 0] 0;
                [above =0.1cm of 1]1;
                [above =0.1cm of -s] -s;
                [above =0.1 cm of s]s;
                [above =0.1cm of -s-1] -s-1;
                [above =0.1cm of s+1] s+1;
                (-1) .. controls (-0.75, 0.5) and (-0.25,0.5) .. (0);
                (-1) .. controls (-0.75, -0.5) and (-0.25,-0.5) .. (0);
                (0) .. controls (0.25, 0.5) and (0.75,0.5) .. (1);
                (0) .. controls (0.25, -0.5) and (0.75,-0.5) .. (1);
                (-1) .. controls (-1.25, 0.5) and (-1.75,0.5) .. (-1.9,0.2);
                (-1) .. controls (-1.25, -0.5) and (-1.75,-0.5) .. (-1.9,-0.2);
                [dashed] (-2.1,0) – (-2.9,0);
                (-3.1,0.2) .. controls (-3.25, 0.5) and (-3.75,0.5) .. (-s);
                (-3.1,-0.2) .. controls (-3.25, -0.5) and (-3.75,-0.5) .. (-s);
                (1) .. controls (1.25, 0.5) and (1.75,0.5) .. (1.9,0.2);
                (1) .. controls (1.25, -0.5) and (1.75,-0.5) .. (1.9,-0.2);
                [dashed] (2.1,0) – (2.9,0);
                (3.1,0.2) .. controls (3.25,0.5) and (3.75,0.5) .. (s);
                (3.1,-0.2) .. controls (3.25,-0.5) and (3.75,-0.5) .. (s);
                [blue, thick] (-s) .. controls (-4.25, 0.5) and (-4.75,0.5) .. (-s-1);
                [blue, thick] (-s) .. controls (-4.25, -0.5) and (-4.75,-0.5) .. (-s-1);
                [blue, thick] (s) .. controls (4.25, 0.5) and (4.75,0.5) .. (s+1);
                [blue, thick] (s) .. controls (4.25, -0.5) and (4.75,-0.5) .. (s+1);
                [dashed] (-s-1) – (-6,0);
                [dashed] (s+1) – (6,0);
            
        

    
    
    
        
  * If at stage s we see that x(e,s-1)=0 and x(e,s)=1 (namely, our approximation changes its mind and puts e into X), we add two edges between -s and s, then we add one edge between both s,s+1 and s, -(s+1), while putting no edge between -s and -(s+1).
    
    
        

            
                at (-1,0) (-1) ∙;
                at (0,0) (0) ∙;
                at (1,0) (1) ∙;
                at (-2,0) (-s+1) ∙;
                at (2,0) (s-1) ∙;
                at (-3,0) (-s) ∙;
                at (3,0) (s) ∙;
                at (-4,0) (-s-1) ∙;
                at (4,0) (s+1) ∙;
                [above =0.1cm of -1] -1;
                [above =0.1cm of 0] 0;
                [above =0.1cm of 1]1;
                [above =0.1cm of -s] -s;
                [above =0.1 cm of s]s;
                [above =0.1cm of -s-1] -s-1;
                [above =0.1cm of s+1] s+1;
                (-1) .. controls (-0.75, 0.5) and (-0.25,0.5) .. (0);
                (-1) .. controls (-0.75, -0.5) and (-0.25,-0.5) .. (0);
                (0) .. controls (0.25, 0.5) and (0.75,0.5) .. (1);
                (0) .. controls (0.25, -0.5) and (0.75,-0.5) .. (1);
                [dashed] (-1.2,0) – (-1.8,0);
                (-s+1) .. controls (-2.25, 0.5) and (-2.75,0.5) .. (-s);
                (-s+1) .. controls (-2.25, -0.5) and (-2.75,-0.5) .. (-s);
                [dashed] (1.2,0) – (1.8,0);
                (s-1) .. controls (2.25,0.5) and (2.75,0.5) .. (s);
                (s-1) .. controls (2.25,-0.5) and (2.75,-0.5) .. (s);
                [blue, thick] (s) – (s+1);
                [blue, thick] (-s-1) .. controls (-2.7,-2.5) and (2.7,-2.5) .. (s);
                [blue, thick] (-s) .. controls (-2.5,-1.5) and (2.5,-1.5) .. (s);
                [blue, thick] (-s) .. controls (-2.5,-2) and (2.5,-2) .. (s);
                [dashed] (-s-1) – (-5,0);
                [dashed] (s+1) – (5,0);
            
        

    
    
    
        
  * We keep adding one edgee between both s, s+1 and -s, -(s+1) until we see that x(e,s-1)=x(e,s)=1 (that is, our computable approximation believes that e ∈ X).
    
    
        

            
                at (0,0) (0) ∙;
                at (.75,0.5) (0') ∙;
                at (-.75,0.5) (0”) ∙;
                (0) to[bend left] (0'); 
                (0) to[bend right] (0'); 
                (0) to[bend left] (0”); 
                (0) to[bend right] (0”); 
                at (0.75,1.25) (1') ∙;
                at (-0.75,1.25) (1”) ∙;
                at (0,1.75) (1”') ∙;
                (1') to[bend left] (1”'); 
                (1') to[bend right] (1”');
                (1”) to[bend left] (1”'); 
                (1”) to[bend right] (1”'); 
                [dashed] (0') to[bend right] (1');
                [dashed] (0”) to[bend left] (1”);
                at (1,0) (1) ∙;
                at (-1,0) (-1) ∙;
                (0) – (1);
                (0) – (-1);
                at (2,0) (s) ∙;
                [above =0.1 cm of s] s;
                at (-2,0) (-s) ∙;
                [above =0.1 cm  of -s] -s;
                [dashed] (1) – (s);
                [dashed] (-1) – (-s);
                at (3,0) (s+1) ∙;
                [above =0.1 cm of s+1] s+1;
                at (-3,0) (-s-1) ∙;
                [above =0.1 cm of -s-1] -s-1;
                [blue, thick] (s) – (s+1);
                [blue, thick] (-s) – (-s-1);
                [dashed] (s+1) – (4,0);
                [dashed] (-s-1) – (-4,0);
            
        

    
    
    
        
  * If at stage s we see that x(e,s-1)=1 and x(e,s)=0 (namely, our approximation changes its mind again and removes e from X), we add one edge between -s and s, then we add two edges between both s,s+1 and s, -(s+1), while putting no edge between -s and -(s+1).
    
    
        

            
                at (0,0) (0) ∙;
                at (.75,0.5) (0') ∙;
                at (-.75,0.5) (0”) ∙;
                (0) to[bend left] (0'); 
                (0) to[bend right] (0'); 
                (0) to[bend left] (0”); 
                (0) to[bend right] (0”); 
                at (0.75,1.25) (1') ∙;
                at (-0.75,1.25) (1”) ∙;
                at (0,1.75) (1”') ∙;
                (1') to[bend left] (1”'); 
                (1') to[bend right] (1”');
                (1”) to[bend left] (1”'); 
                (1”) to[bend right] (1”'); 
                [dashed] (0') to[bend right] (1');
                [dashed] (0”) to[bend left] (1”);
                at (1,0) (1) ∙;
                at (-1,0) (-1) ∙;
                (0) – (1);
                (0) – (-1);
                at (2,0) (2) ∙;
                at (3,0) (s) ∙;
                [above =0.1 cm of s] s;
                at (-2,0) (-2) ∙;
                at (-3,0) (-s) ∙;
                [above =0.1 cm  of -s] -s;
                [dashed] (1) – (2);
                [dashed] (-1) – (-2);
                (2) – (s);
                (-2) – (-s);
                at (4,0) (s+1) ∙;
                [above =0.1 cm of s+1] s+1;
                at (-4,0) (-s-1) ∙;
                [above =0.1 cm of -s-1] -s-1;
                [dashed] (s+1) – (5,0);
                [dashed] (-s-1) – (-5,0);
                [blue, thick] (s) .. controls (3.25,0.5) and (3.75,0.5) .. (s+1);
                [blue, thick] (s) .. controls (3.25,-0.5) and (3.75,-0.5) .. (s+1);
                [blue, thick] (-s) .. controls (-2.5,-1) and (2.5,-1).. (s);
                [blue, thick] (-s-1) .. controls (-2.7,-1.5) and (2.7,-1.5) .. (s);
                [blue, thick] (-s-1) .. controls (-2.7,-2) and (2.7,-2) .. (s);
            
        

    
    
    
        
  * We restart from item (1).
    
    
        

            [rotate=90]
                at (0,0) (0) ∙;
                at (.75,0.5) (0') ∙;
                at (-.75,0.5) (0”) ∙; 
                (0) to[bend right] (0'); 
                (0) to[bend left] (0”); 
                at (0.75,1.25) (0”') ∙;
                at (-0.75,1.25) (0””) ∙;
                [dashed] (0') to[bend right] (0”');
                [dashed] (0”) to[bend left] (0””);
                at (0,1.75) (0””') ∙;
                (0”') to[bend right] (0””');
                (0””) to[bend left] (0””');
                at (.75,2.25) (1') ∙;
                at (-.75,2.25) (1”) ∙;
                (0””') to[bend left] (1'); 
                (0””') to[bend right] (1'); 
                (0””') to[bend left] (1”); 
                (0””') to[bend right] (1”);
                at (.75,3) (1”') ∙;
                at (-.75,3) (1””) ∙;
                at (0,3.5) (1””') ∙;
                [dashed] (1') to[bend right] (1”');
                [dashed] (1”) to[bend left] (1””);
                (1”') to[bend right] (1””');
                (1”') to[bend left] (1””');
                (1””) to[bend right] (1””');
                (1””) to[bend left] (1””');
                at (-.75,-.5) (-1) ∙;
                at (.75,-.5) (1) ∙;
                [blue, thick] (0) to[bend right] (1);
                [blue, thick] (0) to[bend left] (1);
                [blue, thick] (0) to[bend right] (-1);
                [blue, thick] (0) to[bend left] (-1);
                [dashed] (1) – (1.5,-1);
                [dashed] (-1) – (-1.5,-1);
            
        

    
    
    Notice that the graph G_e constructed in such a way always has two ends. Indeed, since X ∈Δ_2^0, there must be a stage s^* with x(e,s)=x(e,s^*) for all s≥ s^*: hence, we do not create new cycles after such stage.
    
    Now, let s_0=0 and let {s_1, …, s_k} be the set of all  stages in which x(e, ·  ), labeled in increasing order. In other words, those stages s with x(e,s -1)  x(e,s)). By our assumption, e ∈ X if and only if k is odd. Thus, it remains to show that G_e admits a two-way infinite Eulerian path if and only if k is odd. First, observe that every vertex in G_e has even degree. Moreover, observe that the graph G_e[{v | |v| ≥ s_k}] is an infinite, connected graph: hence, for any finite set F of edges such that each of them connects two vertices x,y with max{|x|,|y| }≤ s_k, the graph G_e ∖ F has only one infinite connected component. Now, assume that k is odd. Then every vertex in G_e[{v | |v| ≥ s_k}] has degree 2: thus, any finite set of edges from G_e[{v | |v| ≥ s_k}] will induce a subgraph which is not even. This proves that if k is odd, then G_e satisfies . On the other hand, if k is even, every vertex in G_e[{v | |v| ≥ s_k] has degree 4: removing both edges connecting s_k and s_k+1, and those connecting s_k and -(s_k+1) we are left with two infinite connected components, namely G_e[{ v ≥ s_k+1 }] and G_e[{ v ≤ -(s_k+1) }]. This shows that for k even, the graph G_e does not satisfy . 
    
    
    


    
       
        


            [scale=0.8]
                
                at (-6.5,0) ⋯;
                at (-6,0) (0) ∙;
                [-] (-6,0) – (-5,0);
                at (-5,0) (0) ∙;
                [-] (-4,0) – (-5,0);
                at (-4,0) (0) ∙;
                at (-4,1) (0) finite
even
graph;
                [black] (-4,1) ellipse (0.5cm and 1cm);
                
                
                at (-4,-1) G_e for e odd;
                at (-3,0) ∙;
                [-] (-4,0) – (-3,0);
                [-] (-3,0) – (-2,0);
                at (-2,0) ∙;
                at (-1.5,0) ⋯;
                
                
                
                at (6.5,0) ⋯;
                at (6,0) (6) ∙;
                [black] (5.5,0) ellipse (0.5cm and 0.2cm);
                at (5,0) (5) ∙;
                [black] (4.5,0) ellipse (0.5cm and 0.2cm);
                at (4,0) (4) ∙;
                at (4,1) finite
even
graph;
                
                at (4,-1) G_e for e even;
                [black] (4,1) ellipse (0.5cm and 1cm);
                [black] (3.5,0) ellipse (0.5cm and 0.2cm);
                at (3,0) (3) ∙;
                [black] (2.5,0) ellipse (0.5cm and 0.2cm);
                at (2,0) (2) ∙;
                at (1.5,0) ⋯;
                
            
        

    
    


 §.§ The case of non-locally finite graphs

With minor modifications, all our results about the difficulty of the Eulerian Path problem for highly computable graphs are also valid for the larger class of computable graphs for which the vertex degree function _G V(G)→∪{∞} is computable, and which are not necessarily locally finite. This includes <Ref>, <Ref>, <Ref>, <Ref>, <Ref>, and <Ref>. Indeed, all the lower bounds that we proved are valid in this more general context, simply because we proved the lower bounds for highly computable graphs, and we are now considering a class of graphs that includes highly computable graphs. 

Regarding the upper bounds for  and , observe that the conditions on the vertex degrees now include vertices with infinite degree, but upper bounds remain intact as “v has infinite degree” is a decidable predicate of v. Moreover, all results from <Ref> are still available, as explained in <Ref>. By this we refer specifically to the fact that E→_G(E) is upper-semicomputable, uniformly on G, and to <Ref>. These are the key facts that allowed us to prove the upper bounds in <Ref>, <Ref>, <Ref>, <Ref>, <Ref>, and <Ref>.



Let G be a computable graph for which the function _G V(G)→ is computable, with no extra assumptions, and an unknown number of ends. We claim that the problem of determining whether G satisfies  (resp. ) is Π_2^0-complete. Let us first consider the upper bound for the conditions . Determining whether G is connected and infinite is clearly a Π_2^0 problem. The condition that every vertex has either even or infinite degree is clearly Π_1^0. Moreover, as E→_G(E) is an upper-semicomputable function, uniformly on G (see <Ref>), we have that determining whether G has at most  two ends is a Π_2^0 problem. The condition that for every E⋐ E(G) for which G[E] is an even graph, G∖ E has exactly one infinite connected component, can be written as 

    (∀ E ⋐ E(G))(∃ n∈)   ((∃ v ∈ G[E])  _G[E](v) is odd)  (_G,n(E)≤ 1),

so it is Π_2^0 again. It follows that the problem of determining whether G satisfies  is Π_2^0. These arguments can be easily extended to the  case. Finally, the lower bounds follow from the constructions in <Ref> and <Ref>.

This shows that the problem of determining whether an infinite graph G admits a one-way or two-way infinite Eulerian path is Π_2^0. The lower bound 



 §.§ Decidability in the automatic case


The definition of automatic graph is a special case of that of automatic structure  <cit.>. This roughly means that the vertex set and adjacency relation can be understood through words and finite automata on these words. It is natural to wonder whether some problems whose complexity is known for highly computable graphs, become easier for automatic graphs. While there is a number of examples of problems for which this is the case, other problems just keep the same difficulty. As we have mentioned, deciding whether a given general graph is Eulerian belongs to the latter case: it was shown in <cit.> that this is a Π_2-complete problem regardless of whether the graphs are automatic or highly computable.  

As we have shown, however, for highly computable graphs this complexity gets reduced if we restrict ourselves to graphs with only one end. In this section we  prove that for automatic graphs the complexity of this problem gets reduced even more: determining if an automatic graph with one end admits an Eulerian path is decidable. 

We start by giving a brief account for the material on automatic graphs, and refer the reader to <cit.> for more details. Given an undirected graph G, we denote by R(G) the relation of adjacency. An undirected graph G is automatic when the relational structure (V(G),R(G)) admits an automatic presentation: a tuple (Σ,L,R_e,R_a,h) where Σ is a finite alphabet, L⊂Σ^∗ is a regular language, h L→ V(G) is a surjective function, and R_e={(u,v) : h(u)=h(v)}, R_a={(u,v) : R(G)(h(u),h(v))} are regular relations.

Automatic graphs have a decidable first order theory. Even more, the sets that can be defined by first order formulas are regular with respect to an automatic presentation  <cit.>. This proves the decidability of the first order theory, as the emptiness problem for regular languages is decidable. Several works show that we can enrich the first order theory with  counting quantifiers such as  “there are k mod n”, and “there are infinitely many”, and that the sets defined with these formulas are still regular. We will use the following result, which is a direct consequence of <cit.>


    There is an algorithm which, given an automatic graph G, an automatic presentation for (V(G),R(G)), and a sentence written with first order quantifiers plus quantifiers of the form ∃^even (there is an even number), ∃^odd (there is an odd number), and ∃^∞ (there is an infinite number),  returns the truth value of the sentence. 





    There is an algorithm which, on input the automatic presentation of an automatic graph which is connected and has one end, decides whether it satisfies .


    Recall from <Ref> that a graph which is connected and has one end admits a two-way infinite Eulerian path if and only if every vertex has even degree. This condition can be expressed as follows: 
    (∀ u )( ∃ ^even v )R(u,v).

    This is decidable from an automatic presentation by <Ref>. 



    There is an algorithm which, on input the automatic presentation of an automatic graph which is connected and has one end, decides whether it satisfies .


    Recall from <Ref> that a graph which is connected and has one end admits a one-way infinite Eulerian path if and only if it has exactly one vertex with odd degree. This condition can be expressed as follows: 
    (∃ ! u )( ∃ ^odd v ) R(u,v).

    That is,
    
    (∃ u )( ∃ ^odd v)(∀ w)(∃ ^even z) ( R(u,v)   (w=u    R(w,z)).

    This is decidable from an automatic presentation of the graph by <Ref>. 


    We note here that automatic graphs are not necessarily locally finite, and that these proofs can be easily adapted to cover this more general case. Indeed, let G be an automatic graph with one end and which is not locally finite. <Ref> asserts the following: G admits a one-way infinite Eulerian path if and only if either G has exactly one vertex whose degree is odd, or G has at least one vertex with infinite degree and no vertex with odd degree. Moreover, G admits a two-way infinite Eulerian path if and only if all vertices have either even or infinite degree. Now observe that <Ref> allows us to deal with quantifiers of the form “there are infinitely many v”, so the same arguments in Propositions <ref> and <ref> can be extended in a straightforward manner.









§ ON THE COMPLEXITY OF G, G AND THEIR RELASHIONSHIP TO G.


In this section we develop a detailed analysis on the hardness of computing the sets G and G from a description of a highly computable graph G. In a first part we establish that while G is Π_1^0-complete in this uniform setting, the set G is Π_2^0-complete. We also study a version of these problems where we ask to compute just one element in G or G from a description of the G. We found that for this simplified version of the problem, the complexities are ∅' for G and ∅” for G.  

In the second part we explore how the computability of G, G and of G interact with each other. We find that the information provided by G is equivalent to the information provided by the combination of G and G, in the sense that there is an algorithm that uniformly transforms one into the other, and vice-versa. We also obtain some negative results, mainly establishing that, individually, the information provided by G is essentially independent from the information provided by G. 





 §.§ The complexity of G


We have already establish in <Ref> that while for every G with finitely many ends there is an algorithm that decides G, doing it so with an algorithm uniform in G is a Π_1^0 problem in general. Here we prove that this upper bound is in fact tight.  More precisely, we show that every function f: ⟶ mapping a highly computable graph G with (at least) two ends into some element of G –a witness of separation– satisfies f≥_T. Moreover, as our construction shows, this is the case even if we restrict ourselves to graphs that are trees. 


    There is a uniformly highly computable sequence (G_e)_e ∈ of graphs, all of them trees and with two ends, such that: 
        
            
  * {e |{(0,1) }∈G_e} is Π_1^0-complete; 
            
  * Let f be such that  f(e) ∈G_e for every e∈. Then f ≥_T.
        



     We have already established the Π_1^0 upper bound in <Ref>. It remains to show the Π_1^0-completeness.
         Let (φ_e)_e ∈ be a computable enumeration of Turing machines without input. We define G_e as follows: we let V(G_e) = and 
    E(G_e)={(s,s+1)| s∈}∪{(-s-1,s+1)|φ_e,s-1↑ and φ_e,s↓}∪{(-s,-s-1)| (φ_e,s-1↑ and φ_e,s↑)  or  (φ_e,s-1↓ and φ_e,s↓)  }.
    
    In other words, at every stage s we check whether the computation φ_e,s halts.

   As long as φ_e,s↑, we keep adding both the edge between s and s+1 and the edge between -s and -s-1. 

    
        

            
                at (-1,0) (-1) ∙;
                at (0,0) (0) ∙;
                at (1,0) (1) ∙;
                at (-4,0) (-s) ∙;
                at (4,0) (s) ∙;
                at (-5,0) (-s-1) ∙;
                at (5,0) (s+1) ∙;
                [above = 0 cm of -1] -1;
                [above = 0 cm of 0] 0;
                [above = 0 cm of 1] 1;
                [above = 0 cm of -s] -s;
                [above = 0 cm of s] s;
                [above = 0 cm of -s-1] -s-1;
                [above = 0 cm of s+1]  s+1;
                (-1) – (0);
                (0) – (1);
                (-1) – (-2,0);
                [dashed] (-2.1,0) – (-2.9,0);
                (-3,0) – (-s);
                (1) – (2,0);
                [dashed] (2.1,0) – (2.9,0);
                (3,0) – (s);
                [blue, thick] (-s) – (-s-1);
                [blue, thick] (s) – (s+1);
                [dashed] (-s-1) – (-6,0);
                [dashed] (s+1) – (6,0);
            
        

    

    Hence, if φ_e ↑, G_e will look as follows:
    
        

            
                at (0,0) (0) ∙;
                [above = 0 cm of 0] 0;
                (-2,0) – (0);
                (2,0) – (0);
                [dashed] (-2.1,0) – (-2.6,0);
                [dashed] (2.1,0) – (2.6,0);
            
        

    

    But if φ_e,s↓, we still put edge between s and s+1, while omitting the edge between -s and -s-1. Instead, we put an edge between s+1 and -s-1.

    
        

             
                at (-1,0) (-1) ∙;
                at (0,0) (0) ∙;
                at (1,0) (1) ∙;
                at (-4,0) (-s) ∙;
                at (4,0) (s) ∙;
                at (-5,0) (-s-1) ∙;
                at (5,0) (s+1) ∙;
                [above = 0 cm of -1] -1;
                [above = 0 cm of 0] 0;
                [above = 0 cm of 1] 1;
                [above = 0 cm of -s] -s;
                [above = 0 cm of s] s;
                [above = 0 cm of -s-1] -s-1;
                [above = 0 cm of s+1]  s+1;
                (-1) – (0);
                (0) – (1);
                (-1) – (-2,0);
                [dashed] (-2.1,0) – (-2.9,0);
                (-3,0) – (-s);
                (1) – (2,0);
                [dashed] (2.1,0) – (2.9,0);
                (3,0) – (s);
                [blue] (s) – (s+1);
                [blue, thick] (-s-1) .. controls (-2,-1) and (2,-1) .. (s+1);
                [dashed] (-s-1) – (-6,0);
                [dashed] (s+1) – (6,0);
            
        

    

    Hence, in this case G_e will look like this:

    
        

             
                at (0,0) (s) ∙;
                [below = 0 cm of s] s;
                (-2,0) – (s);
                (2,0) – (s);
                [dashed] (-2.1,0) – (-2.6,0);
                [dashed] (2.1,0) – (2.6,0);
                at (0,1) (0) ∙;
                [left = 0 cm of 0] 0;
                at (0,2) (-s) ∙;
                [left = 0 cm of -s] -s;
                (s) – (0) – (-s);
            
        

    

    The G_e's are clearly uniformly highly computable.
    
    Notice that the singleton {(0,1) } separates G_e if and only if φ_e does not halt, that is e ∈. This proves item 1.

    For proving item 2 observe that: 
    
        
  * if (x,y) ∈G_e and y ∉{ x-1, x+1 }, then φ_e halts;
        
  * if φ_e halts, then {(x,x+1)}∈ E(G_e) separates G_e if and only if max{|x|,|x+1|} is larger than the minimum number of steps in which φ_e halts (notice that in this case (-s,-(s+1)) ∉ E(G_e)).
    
    Now suppose we are given a function f: → such that f(e) ∈G_e. First we check whether there is  (x,y) ∈ f(e) such that y ∉{ x-1, x+1 }, in which case we are sure that e ∈. Otherwise, let n = max{|v| | v  is incident to some edge in f(e) } and run φ_e for n steps: then e ∈ if and only if φ_e,n↓.  
    

We end our analysis of G by considering the case of graphs with infinitely many ends. As shown in the next result, in this case G may become undecidable even in the non uniform regime.  


    There is a connected highly computable graph G with infinitely many ends for which G≡_T.

 Fix a computable enumeration (φ_e)_e ∈ of Turing machines without input.

    We define a graph G as follows. Its set of vertices is V(G) = { (e,s):  φ_e,s↑}⊂^2, and its set of edges is E(G) = {((e,0),(e+1,0):  e ∈}∪{((e,s-1),(e,s)):  φ_e,s↑}.
    
    For example, in case φ_0 and φ_2 halts but φ_1 doesn't, G would look something like the picture below.
    
    



    
        at (0,0) (0) ∙;
        [below = 0 cm of 0] (0,0);
        at (1.5,0) (1) ∙;
        [below = 0 cm of 1] (1,0);
        at (3,0) (2) ∙;
        [below = 0 cm of 2] (2,0);
        (0) – (1);
        (1) – (2);
        (2) – (4,0);
        [dashed] (4,0) – (4.75,0);
        at (0,1.5) (0') ∙;
        [left = 0 cm of 0'] (1,0);
        at (1.5,1.5) (1') ∙;
        [left = 0 cm of 1'] (1,1);
        at (3,1.5) (2') ∙;
        [left = 0 cm of 2'] (2,1);
        at (0,3) (0”) ∙;
        [left = 0 cm of 0”] (2,0);
        at (1.5,3) (1”) ∙;
        [left = 0 cm of 1”] (2,1);
        at (1.5,4.5) (1”') ∙;
        [left = 0 cm of 1”'] (3,1);
        (0) – (0');
        (0') – (0”);
        (1) – (1');
        (1') – (1”);
        (1”) – (1”');
        (1”') – (1.5, 5.5);
        [dashed] (1.5,5.5) – (1.5, 6.25);
        (2) – (2');
    
    
    

    
    
    

    Observe that G is highly computable. Indeed, V(G) and E(G) are clearly computable. Moreover, for each (e,s) ∈ V(G), we have

    
    deg_G((e,s)) = 
            1,     if ((e=s=0)  or (e>0  and s>0))  and φ_e,s+1↓
    
            3,     if (e>0  and s=0)  and φ_e,s+1↑
    
            2,     otherwise,

    which, again, is clearly computable. 

    

    Observe that the set {((e,s),(e,s+1)) : s ∈} is contained in E(G) if and only if φ_e does not halt. Moreover, in this case, removing the edge from (e,0) to (e,1)  separates G into two infinite connected components - namely, the infinite path P = ((e,t),(e,t+1))_t > 1 and G ∖ (P ∪(e,s)), where the latter contains the infinite path ((n,0),(n+1,0))_n > e.  
    Assume that G is decidable. Then we can decide whether ((e,0),(e,1)) ∈G, which is equivalent to decide whether φ_e ∈ (the complement of the halting set), a contradiction.









 §.§ The complexity of G


Here we show that the complexity of  computing G is strictly higher than that for G. 

The problem of given a highly computable graph G and E⋐ E(G), to determine whether E∈G, is Π_2^0-complete. 



Recall that in <Ref> we defined _G,n(E) as the number of infinite connected components of G∖ E that we can distinguish by inspecting a ball of radius n. This value is computable from a description of a highly computable graph G, E⋐ E(G) and n∈. Observe that E⋐ E(G) lies in G if and only if 

    (∀ F⋐ E(G))(∃ n∈)(_G,n(F)≤_G,n(E)).

This proves the upper bound in the statement.  For the lower bound, we use the sequence of highly computable graphs (G_e^2)_e ∈ constructed in the proof of <Ref>. Recall that graphs of this family have either two or three ends. Consider the edge (0,1), with the vertex 1 taken in the additional copy of ∖{0}: for this family it clearly holds that 
    {e:   (0,1) ∈G_e^2} = {e:   G_e^2  has 2 ends}.




      
        

           
                at (0,0) (0) ∙;
                at (1,0) (s0) ∙;
                at (2,0) (s*) ∙;
                (0) to[bend left] (s0);
                (0) to[bend right] (s0);
                [dashed] (s0) – (s*);
                (s*) – ++(20:0.75cm);
                [dashed] (s*)++(20:0.75cm) – ++(20:0.75cm);
                (s*) – ++(-20:0.75cm);
                [dashed] (s*)++(-20:0.75cm) – ++(-20:0.75cm);
                [above = 0 cm of 0] 0;
                [above = 0 cm of s*] s^*;
                at (-1,0) (1) ∙;
                [above= 0 cm of 1] 1;
                [thick, blue, dotted] (0) – (1) node[midway] ×;
                (1) – ++(180:0.75 cm);
                [dashed] (1)++(180:0.75 cm) – ++(180:0.75 cm);
                (L) at ((1)+(180:1.5 cm));
                (C1) at ((s*)+(20:1.5cm));
                (C2) at ((s*)+(-20:1.5cm));
                (R) at (0.5*(C1)+0.5*(C2));
                [decorate,decoration=brace,amplitude=5pt,mirror,raise=4ex] (L) – (1) node[midway, yshift=-3em] 1 end;
                [decorate,decoration=brace,amplitude=5pt,mirror,raise=4ex] (0) – (R) node[midway, yshift=-3em] 2 ends;
            
                    
                at (0,0) (0) ∙;
                at (1,0) (s0) ∙;
                at (2.1,0) (s1) ;
                [above = 0 cm of 0] 0;
                (0) to[bend left] (s0);
                (0) to[bend right] (s0);
                [dashed] (s0) – (s1);
                at (-1,0) (1) ∙;
                [above= 0 cm of 1] 1;
                [thick, blue, dotted] (0) – (1) node[midway] ×;
                (1) – ++(180:0.75 cm);
                [dashed] (1)++(180:0.75 cm) – ++(180:0.75 cm);
                [decorate,decoration=brace,amplitude=5pt,mirror,raise=4ex] (1)++(180:1.5cm) – (1) node[midway, yshift=-3em] 1 end;
                [decorate,decoration=brace,amplitude=5pt,mirror,raise=4ex] (0) – (s1) node[midway, yshift=-3em] 1 end;
              
            
        

    
    Hence, the claim follows immediately from the fact that the set on the right hand side is Π_2^0-complete.
    


    We finish this part by showing the announced lower bound for the simplified version of uniformly computing an arbitrary element in G. 


Let f be a function which, given a highly computable connected
graph G with finitely many ends, outputs an element f(G)∈G.
Then f≥_T0”. 


The proof will rely on the following lemma. 

    Let G be an infinite, connected, and locally finite graph, and let w_0 be a vertex in G. For each r∈ let V_r be the set of vertices in G whose distance to w_0 equals r or r-1, and let E_r be the set of edges in the induced subgraph G[V_r]. Suppose further that E_r∈G. 
    
    Then a subset E⊂ E_r is  minimal for inclusion within G if and only if there is an infinite connected component C of G∖ E_r, such that E equals the set of all edges in E_r incident to some vertex from C. 


For the forward implication, let E⊂ E_r, suppose that E lies in G, and that any proper subset of E is not in G. As E∈G, the graph G∖ E has at least two infinite
connected components. We claim that there is an infinite connected component C of G∖ E_r, such that the set E contains 
all edges that join some vertex in {v∈ V(G)| d(v,w_0)≤ r-1}
to some vertex from C. This follows from the fact that the graph G[{v∈ V(G)| d(v,w_0)≤ r-1}] is connected: if C does not exist, then every infinite connected component in G∖ E is connected to G[{v∈ V(G)| d(v,w_0)≤ r-1}], implying that G∖ E has exactly one infinite connected component. This contradicts the fact that E∈G, so the component C exists. Moreover, if E contains edges  that are not joined to vertices in C, then we can discard them while still
having an element in G, contradicting that E is minimal for inclusion. This proves the forward implication, and the backward implication is clear.



Let f be a function as in the statement. Note that if G has
two ends, then G=G. Then it follows from <Ref> that f≥_T0'.
Then, by <Ref>, f can
be used to decide membership in G, with a procedure that
is uniform on a description of G. 
We claim that the function f can be used to compute the number
of ends of a highly computable and connected graph with finitely many
ends. This can be done as follows. Given the graph G, we compute
E=f(G)∈G. Then we choose a vertex v_0
and r∈ so that the induced subgraph G[{v∈ V(G)| d(v,v_0)≤ r-1}]
contains all edges from E. We then let E_r=E(G[{v∈ V(G)| r-1≤ d(v,v_0)≤ r}}]). Our choice of r ensures that E_r lies in G. 
As we can decide membership in G, we can determine those
subsets of E_r that are minimal for inclusion among those in
G. This information is sufficient to determine the number
of infinite connected components of G∖ E_r by <Ref>. But as E_r∈G, this is the number of ends of G. 
At this point we have proved that the function f can be used to compute the number
of ends of a highly computable connected graph G with finitely
many ends. Then it follows from Proposition <ref>
that f≥_T0”. 












 §.§ The relationship among G, G and G





In informal words, the main result of this section is the relation:

    G+G=G.

More specifically: 

    Let G be a highly computable graph with finitely many ends. Then:
    
        
  * There is an algorithm which with oracle access to G computes G and G. This algorithm is uniform on  G.
        
  * There is an algorithm which given G and with oracle access to G, decides membership in G. 
    

This result will be proved in several parts.


    There is an algorithm which, given a description of a highly computable graph G which is connected and has finitely many ends, and oracle access to G, computes 
    G. 


    First, observe that ∅∈G if and only if G has only one end. Hence, we can detect if G has only one end. If ∅∉G, then we proceed as follows. We choose a vertex w_0, and define E_r as the set of edges in the induced subgraph G[{v∈ V(G)| d(v,w_0)=r or  d(v,w_0)=r-1}]. Having oracle access to G, we can compute r so that E_r lies in G. We fix from now on E= E_r.  We write E={e_1…,e_n}, and we compute a set of vertices U={u_1,…,u_n} so that d(u_i,w_0)=r, and e_i is incident to u_i.  
    
    Observe that every connected component of G∖ E contains a vertex u_i. We denote by C_i the connected component of G∖ E that contains u_i. Moreover, the number of ends of G equals the number of infinite connected components of G∖ E. In what follows we describe an effective procedure which, with oracle access to G, allows us to decide which components of C_1,…, C_n are infinite, and for which pairs of i and j the component C_i is equal to C_j. 

    
        C_i is infinite if and only if there is a set W ⊂ E minimal for inclusion within G, and that contains an edge incident to u_i.
    
    
    Indeed, suppose that C_i is finite, that W⊂ E lies in G,  and that E 
    contains an edge e that is incident to u_i. Then it is clear that W∖{e} also lies in G, as removing the edge e from W modifies G∖ W only by connecting a finite connected component to a possibly infinite one. It follows that W  also lies in G, so W was not minimal for inclusion in G. We conclude that for C_i finite, any subset W⊂ E that is minimal for inclusion and lies in G has no edge incident to u_i. 
    
    Assume now that C_i is infinite. Since we already ruled out the possibility that G has 1 end, there must be a component C_k different to C_i, and that is also infinite. We choose W⊂ E as the set of all edges in E that are incident to some vertex in an infinite connected component of G∖ E that is different from C_k. Observe that then W contains all edges incident to C_i, and no edge incident to a finite connected component of G∖ E. Moreover, the connected components from  G∖ E that are different from C_k, remain the same in G∖ W. The component C_k of G∖ E, has been modified in G∖ W: it has been connected to the finite graph G[{v∈ V(G)| d(v,w_0)≤ r-1}]. 

    We claim that W is minimal for inclusion in G. Indeed, let e be an arbitrary edge in W, so e is incident to a vertex u_j, with j∈{1,…,n} and  C_k C_j. Observe that, in the graph G∖ (W∖{e}), the vertices u_k and u_j are in the same connected component. This follows from the fact that the graph G[{v∈ V(G)| d(v,w)≤ r-1 }] is connected. In other words, the components C_k and C_j from G∖ E, can be connected in the graph G∖ W', and thus W' does not lie in G. It follows that the set W is minimal for inclusion in G. This proves the claim.

    
        Suppose that both C_i and C_j are infinite. Then C_i=C_j if and only if there is W ⊂ E minimal for inclusion within G, and which contains no edge incident to vertices in C_i or in C_j. 
    

    In the proof of the previous claim we actually proved the forward implication. That is, we proved that if C_i is infinite, then the set W⊂ E of all edges in E that are incident to some vertex in an infinite connected component of G∖ E that is different from C_i, lies in G and is minimal for inclusion within G. If C_i=C_j, then this set W verifies the claim. We now prove the backward implication, suppose that there is W ⊂ E minimal for inclusion within G, and which contains no edge incident to vertices in C_i or in C_j. If the connected components C_i and C_j of G∖ E are infinite and different, then the graph G∖ W has a component with two ends, contradicting that W lies in G. This proves the claim.

    Observe that the conditions in these two claims are decidable with oracle access to G. In other words, we have exhibited an effective procedure that, with oracle access to G, decides which components among C_1,…,C_n are infinite, and which are indeed the same connected component. This allows us to compute the number of infinite connected components of G∖ E, which equals the number of ends of G because E is taken in G.  



    There is an algorithm which, given a description of a highly computable graph G which is connected and has finitely many ends, the number G, and oracle access to G, computes an element in G. 


    Let k be the number of ends of G. We fix a vertex w_0∈ V(G), and for each r∈ we let E_r be the set of edges in the induced subgraph {v∈ V(G)| d(v,w_0)=r or d(v,w_0)=r-1}. It is clear that for r big enough, the set E_r lies in G. The next claim follows directly from <Ref>:
    
        E_r lies in G if and only if the following two conditions are satisfied:
    
        
  * If E,E' are subsets of E_r, both lie in G, and both are minimal for inclusion within G, then E,E'  are either disjoint or equal. 
        
  * E_r has exactly k subsets which are in G and are minimal for inclusion within G.
         
     
    As these conditions are decidable with oracle access to G, we have an effective procedure that, given r∈ and having oracle access to G, determines whether E_r lies in G. But then we can compute a set E_r that lies in G by an exhaustive search.





    Let k be the number of ends of G. We fix a vertex v∈ V(G), and from now on we write B_r=B_r(v), r∈. We define U_r={u∈ V(G)| d(u,v)=r}. 
    We say that r∈ satisfies ⋆ if the following conditions hold:
    
        
  * | {V ∈G∩ U_r:  V' ⊂ V  V' ∉G}| = k, namely U_r has exactly k subsets which are in G and are minimal for inclusion within G; and
        
  * every pair V,V' of subsets of U_r which lie in G and are minimal for inclusion among subsets of G are either disjoint or the same set.
    
    
    
        There is r_0 such that every r≥ r_0 satisfies ⋆.
    
    It is clear from the definition that if r satisfies ⋆, then r+1 also satisfies ⋆. Hence it is enough to prove that if U_r lies in G, then U_r+1 satisfies ⋆. Let U_r ∈G, and let C_1,…,C_k be the infinite connected components of G-U_r. 

    Without loss of generality, we assume that U_r doesn't satisfy ⋆. Then we claim that U_r+1 must satisfy that for every v∈ U_r, there is at most one infinite connected component from G-U_r adjacent to v. Notice that this property implies ⋆. Since U_r+1 lies in G, there are k infinite connected components C_1',…,C_k', where C_i'⊂ C_i. Assume for a contradiction that some v∈ U_r+1 is adjacent to at least two infinite connected components C_i'≠ C_j', say at vertices u_i∈ C_i' and u_j∈ C_j', and let v' be a vertex in U_r adjacent to v. This shows that components C_i and C_j share a vertex v, contradicting the fact that G-U_r has k infinite connected components. 

    
    

    
        If r satisfies ⋆, then U_r lies in G. 
    
    Let V⊂ U_r be a set in G and minimal for inclusion among sets in G. This ensures the existence of an infinite connected component C of G-U_r which is adjacent to V, and which is not adjacent to any other V'≠ V which lies in G and is minimal for inclusion. Indeed, if every infinite connected component of G-U_r which is adjacent to V is also adjacent to some other V', then V does not lie in G. 
    Thus every subset V⊂ U_r which is in G and is minimal for inclusion has at least one adjacent infinite connected component in G-U_r, and which is not adjacent to any other such V'. This proves that G-U_r has at least k infinite connected components, and thus U_r lies in G. 
    This finishes the proof.


We are now ready to prove <Ref>.

    The main tool in this proof is <Ref>. Let us start by proving the first item in <Ref>. Given a graph G as in the statement and oracle access to G, we can compute G with the algorithm in <Ref>. Putting this together with the function in <Ref>, we obtain an algorithm to decide membership in G. 

    We now prove the second item in  <Ref>. Given a graph G as in the statement and oracle access to G, we can compute an element in G with the algorithm in <Ref>. Now we have the information required by the function in <Ref>. This is sufficient to decide membership in G: on input E⋐ E(G), we just have to use the function from <Ref> to compute the number of infinite connected components of G∖ E. If this number equals G, then we conclude that E∈G, and otherwise E∉G.




 §.§ G and G are independent

Here we show that having access to G is not enough to compute G with a procedure uniform on G, and vice versa. This shows that <Ref> cannot be improved significantly.

We first observe that having access to G is not enough to compute G, even if the graphs are assumed to be trees. 

    There is a uniformly highly computable sequence of trees (G_e)_e∈ such that G is uniformly computable, but G is not. 
 

    The sequence defined in the proof of <Ref> satisfies this.

Similarly, we observe that having access to G is not enough to compute G, even if the graphs are assumed to be trees. 

    There is a uniformly highly computable sequence of trees (G_e)_e∈ such that G is uniformly computable, but G is not.


 Fix a computable enumeration (φ_e)_e ∈ of Turing machines without input. Let V(G_e) = ∪{ -s' | s ∈∖{0}}∪{s' |φ_e,s-1↓} (in other words, V(G_e) consists of 0, two copies of the negative integers, a copy of the positive integers and another copy of all the positive integers larger than the number of steps required to φ_e to halt, if any) and 

    E(G_e) = { (s,s+1) | s ∈}∪{ (0,1') }∪{ (-s', (-s-1)') | s ∈∖{0}}∪{(s', (s+1)') |φ_e,s-1↓}.

The following picture shows how each G_e roughly looks like, depending on whether φ_e halts.

    
        

            

            
            
            
                
                at (0,0) (0) ∙;
                [above = 0 cm of 0] 0;
                (0) – (150:0.75cm);
                [dashed] (150:0.75cm) – (150:1.5cm);
                (0) – (-150:0.75cm);
                [dashed] (-150:0.75cm) – (-150:1.5cm);
                (0) – (0:0.75cm);
                [dashed] (0:0.75cm) – (0:1.5 cm);
                [below = 1 cm of 0] G_e for φ_e ↑;
                
                
                
                
                
              
            
                        
                
                at (0,0) (0) ∙;
                [above = 0 cm of 0] 0;
                (0) – (150:0.75cm);
                [dashed] (150:0.75cm) – (150:1.5cm);
                (0) – (-150:0.75cm);
                [dashed] (-150:0.75cm) – (-150:1.5cm);
                (0) – (0:0.75cm);
                [dashed] (0:0.75cm) – (0:1.5 cm);
                at (1.25,0) (M) ;
                [below = 1cm of M] G_e for φ_e ↓;

                at (0:2.4cm) (s) ∙;
                [above= 0 cm of s] s;
                (0:1.6cm) – (s);
                [blue, thick] (s) – ++(30:0.75cm);
                [blue,dashed, thick] (s)++(30:0.75cm) – ++(30:0.75cm);
                 (s) – ++(-30:0.75cm);
                [dashed] (s)++(-30:0.75cm) – ++(-30:0.75cm);
            
            
   
        

    

    It is clear that G_e is uniformly decidable as for each e, G_e is a tree without finite branches and therefore G_e contains all finite sets of vertices. On the other hand, an “additional end" will appear exactly when φ_e halts: hence, the number of ends of these graphs must be uncomputable.







