# the characterization of infinite eulerian graphs, a short and computable
proof

Nicanor Carrasco-Vargas

###### Abstract.

In this paper we present a short proof of a theorem by Erdős, Grünwald and
Weiszfeld on the characterization of infinite graphs which admit infinite
Eulerian trails. In addition, we extend this result with a characterization of
which finite trails can be extended to infinite Eulerian trails.

Our proof is computable and yields an effective version of this theorem. This
exhibits stark contrast with other classical results in the theory of infinite
graphs which are not effective.

###### 2020 Mathematics Subject Classification:

05C63, 05C45, 68R10, 03D99, 68Q01

###### Contents

  1. 1 Introduction
  2. 2 Preliminaries
  3. 3 The proof
    1. 3.1 Some considerations
    2. 3.2 The case of one-sided infinite trails
    3. 3.3 The case of two-sided infinite trails
  4. 4 The computability of the proof

##  1\. Introduction

Eulerian trails -which arose from the Königsberg bridge problem- are those
trails which visit every edge of a graph exactly once. In contrast to
Hamiltonian paths and other graph theoretic objects, Eulerian trails are very
tractable from an algorithmic point of view. In this paper we shall see that
this tractability still holds for infinite trails on infinite graphs.

Let us recall the following classical result, which provides a criterion on
the existence of closed and non closed Eulerian trails for finite graphs.

######  Theorem (Euler’s theorem).

Let $\Gamma$ be a finite graph. Then $\Gamma$ admits a closed Eulerian trail
if and only if it is connected and all vertices have even degree.

Moreover, $\Gamma$ admits an Eulerian trail from $u$ to $v\neq u$ if and only
if it is connected and $u$, $v$ are the only vertices with odd degree.

König asked for a generalization of this result to infinite graphs and
infinite Eulerian trails, and a relatively simple characterization was
announced in 1936 by Erdős, Grünwald and Weiszfeld. This theorem completely
characterizes which graphs admit one-sided infinite Eulerian trails, whose
vertex set is indexed by $\mathbb{N}$, and two-sided infinite Eulerian trails,
whose vertex set is indexed by $\mathbb{Z}$ (an example is shown in Figure 1
on page 1). The graphs under consideration are undirected, multiple edges with
the same endpoints are allowed (multigraphs), and vertices may have infinite
degree.

This theorem anticipated the important concept of ends, defined later in [4,
5]. In this paper we will use the following definition. The number of ends of
a graph $\Gamma$ is the supremum of the number of infinite connected
components of $\Gamma-E$, where $E$ ranges over all finite sets of edges of
$\Gamma$. There are other definitions of ends for infinite graphs. They are
all equivalent as long as we restrict ourselves to locally finite graphs, a
discussion on this topic can be found in [2]. The definition considered here
captures the right notion for our discussion on infinite trails beyond locally
finite graphs. For example, it makes clear that a graph $\Gamma$ which admits
a one-sided infinite Eulerian trail $T$ must have one end. Let us sketch an
argument here.

Let $E$ be a finite set of edges in $\Gamma$. We need to check that $\Gamma-E$
has only one infinite connected component, for which we take $e$ be the first
edge visited by $T$ after visiting all edges in $E$. Now the set of edges
visited by $T$ after $e$ induce an infinite connected component in $\Gamma-E$,
as $T$ shows how to join any pair of vertices there. This must be the only
infinite connected component in $\Gamma-E$ because there are only finitely
many edges visited by $T$ before $e$. This finishes the argument.

Let us review other evident restrictions on a graph which admits a one-sided
infinite Eulerian trail. For example, it is clear that the graph must be
connected, and its edge set must be countably infinite. In addition the vertex
where the trail starts must have either odd or infinite degree, and the
remaining vertices must have even or infinite degree. This list of conditions,
which we call $\mathscr{E}_{1}$, in fact constitutes a characterization.

######  Theorem 1.1 ([3]).

A graph $\Gamma$ admits a one-sided infinite Eulerian trail if and only if it
satisfies the following set of conditions, called $\mathscr{E}_{1}$.

  * $\circ$

$E(\Gamma)$ is countable, infinite, and $\Gamma$ is connected.

  * $\circ$

There exists at most one vertex with odd degree, and there exists at least one
vertex which has odd or infinite degree.

  * $\circ$

$\Gamma$ has one end.

Let us now review the case of two-sided infinite Eulerian trails. It is clear
that a graph which admits a two-sided infinite Eulerian trail must be
connected, its edge set must be countably infinite, and every vertex must have
even or infinite degree. Moreover it must have one or two ends, the argument
being similar to the one provided above. A less evident observation is the
following: if we remove a finite set of edges $E$ which induces an even111A
finite graph all of whose vertices have even degree. subgraph, then there
remains only one infinite connected component. This is an easy parity argument
which we defer for now. This list of conditions, which we call
$\mathbf{\mathscr{E}}_{2}$, in fact constitutes a characterization.

######  Theorem 1.2 ([3]).

A graph $\Gamma$ admits a two-sided infinite Eulerian trail if and only if it
satisfies the following set of conditions, called $\mathbf{\mathscr{E}}_{2}$.

  * $\circ$

$E(\Gamma)$ is countable, infinite, and $\Gamma$ is connected.

  * $\circ$

The degree of each vertex is infinite or even.

  * $\circ$

$\Gamma$ has one or two ends. Moreover, If $E$ is a set of edges which induces
an even subgraph, then $\Gamma-E$ has one infinite connected component.

The main contribution of this paper is a short proof of Theorem 1.1 and
Theorem 1.2. We extend these results by providing a characterization of which
trails can be extended to one-sided or two-sided infinite Eulerian trails
(Corollary 3.7 and Corollary 3.14). As consequence, infinite Eulerian trails
can be defined locally, by successively extending finite trails, and we have a
certain level of control in this process.

Our proof is computable, we exhibit algorithms to compute infinite Eulerian
trails on graphs satisfying $\mathscr{E}_{1}$ or $\mathbf{\mathscr{E}}_{2}$.
This computation occurs locally, by which we mean that at each step the
algorithm works on a finite subgraph of $\Gamma$. In order to deal with
algorithms on infinite graphs we rely on the notion of highly computable
graph, which in simple words is an infinite graph $\Gamma$ with an algorithm
that can compute finite subgraphs of $\Gamma$ of any desired size. The formal
statement is the following.

######  Theorem 1.3.

If a highly computable graph satisfies $\mathscr{E}_{1}$ (respectively
$\mathbf{\mathscr{E}}_{2}$) then it admits a computable one-sided
(respectively two-sided) infinite Eulerian trail.

Thus a highly computable graph admits a one-sided (respectively two-sided)
infinite Eulerian trail if and only if it admits a computable one.

This is remarkable in comparison with other results in the theory of infinite
graphs for which a computable version is not possible. One such result is
König’s infinity lemma, which asserts that an infinite and locally finite
graph has a one-sided infinite path. This result is not effective, in the
sense that there are highly computable graphs satisfying the hypotheses and
which admit no computable infinite path [6]. Therefore it is not possible to
define a one-sided infinite path using local information in a computable
manner. Other results which are not effective include Hall’s matching theorem
for infinite graphs [7], Ramsey’s theorem [10], and 3-colorings [8]. In our
result the hypothesis of highly computable graph cannot be relaxed to the
weaker notion of computable graph, as we will show with an example.

There are some subtleties regarding uniformity in Theorem 1.3, related to
ends. For one ended graphs satisfying $\mathscr{E}_{1}$ or
$\mathbf{\mathscr{E}}_{2}$ we can prove a stronger result, namely that it is
algorithmically decidable whether a finite trail can be extended to an
infinite Eulerian trail (see Proposition 4.4). A consequence of this is that
the corresponding infinite trails can be computed upon a description of the
graph, or in more informal words, a single algorithm works for every graph.
For two-ended graphs satisfying $\mathbf{\mathscr{E}}_{2}$ the situation is
more subtle, and we only prove the existence of a computable two-sided
infinite Eulerian trail.

We end this introduction by mentioning an application of the ideas involved in
the proof presented here. A recent employment of Theorem 1.2 occurred in the
paper [9], where Seward proved that every connected graph with one or two ends
and with vertex degree uniformly bounded by $D$, has an $n$-th power222The
$n$-th power of a graph $\Gamma$ is the graph with the same set of vertices,
and where a pair of vertices is connected by an edge if their distance in
$\Gamma$ is at most $n$. which admits a two-sided infinite Hamiltonian path.
In that proof the number $n$ depends linearly on $D$. This has interesting
consequences in geometric group theory, it shows that every finitely generated
group with one or two ends has a Cayley graph which admits a two-sided
infinite Hamiltonian path. Using the same ideas presented here we were able to
improve Seward’s result. On the one hand we showed that the number $n$ can be
taken to be equal to 3, while on the other hand we weakened the hypothesis by
allowing vertices to have unbounded but finite degree. These results and their
consequences for Cayley graphs are discussed in [1].

Figure 1. A finite portion of two-sided infinite Eulerian trail on the
infinite grid graph. One edge $e$ has been distinguished in the picture with
an arrow. The edges visited by the trail after $e$ have been colored black,
while edges visited by the trail before $e$ have been colored gray.

##  2\. Preliminaries

Throughout this paper we deal with finite and infinite undirected graphs,
where two vertices may be joined by multiple edges and self loops are allowed.
The vertex set of a graph $\Gamma$ is denoted by $V(\Gamma)$, and its edge set
by $E(\Gamma)$. We will assume that the edge and vertex set of a graph are
disjoint.

Each edge joins a pair of vertices. In the case of a simple graph, we may
identify edges with unordered pairs of vertices. For example, we denote by
$\llbracket a,b\rrbracket$ the graph with vertex set
$\\{a,\dots,b\\}\subset\mathbb{Z}$, and with edges of the form $\\{c,c+1\\}$
for $c\in\\{a,\dots,b-1\\}$. The graphs
$\mathbb{\llbracket}\mathbb{N}\mathbb{\rrbracket}$ and
$\mathbb{\llbracket}\mathbb{Z}\mathbb{\rrbracket}$ are defined in a similar
manner.

When two vertices $x,y$ are joined by an edge $e$, they are called adjacent or
neighbors, and $x,e$ are said to be incident. An edge joining a vertex to
itself is a loop. The degree of a vertex $v$ in $\Gamma$, denoted
$\deg_{\Gamma}(v)$, is the amount of edges incident to $v$, where loops are
counted twice.

A graph homomorphism $f:\Gamma^{\prime}\to\Gamma$ is a function
$f:V(\Gamma)\cup E(\Gamma)\to V(\Gamma^{\prime})\cup E(\Gamma^{\prime})$ which
sends vertices to vertices, edges to edges, and is compatible with the
incidence relation.

It will be convenient for us to define trails as graph homomorphisms. A trail
(resp. one-sided infinite trail, resp. two-sided infinite trail) on $\Gamma$
is a graph homomorphism $t:\mathbb{\llbracket}a,b\mathbb{\rrbracket}\to\Gamma$
(resp. $t:\mathbb{\llbracket}\mathbb{N}\mathbb{\rrbracket}\to\Gamma$, resp.
$t:\mathbb{\llbracket}\mathbb{Z}\mathbb{\rrbracket}\to\Gamma$) which does not
repeat edges. We say that $t$ visits the vertices and edges in its image, and
we call it Eulerian when it visits every edge of $\Gamma$ exactly once.

Note that a trail is finite by definition, but we may still write finite trail
to emphasize this. When $t$ is a finite trail we say that $t(a)$ is its
initial vertex and $t(b)$ is its final vertex. We say that $t$ joins $t(a)$ to
$t(b)$, and we call it closed when $t(a)=t(b)$.

It will also be convenient to induce subgraphs from sets of edges. The induced
subgraph by a set of edges $E\subset E(\Gamma)$ is denoted $\Gamma[E]$, its
edge set is $E$, and its vertex set is the set of all vertices incident some
edge in $E$. For a set of edges $E\subset E(\Gamma)$, $\Gamma-E$ denotes the
subgraph induced by the set of edges $E(\Gamma)-E$. That is, we erase from
$\Gamma$ all edges in $E$, and then all vertices that were left without
incident edges. Given a trail $t$ we denote by $E(t)$ the set of edges visited
by $t$, and we denote by $\Gamma-t$ the induced subgraph $\Gamma-E(t)$. We say
that $\Gamma-t$ is obtained by removing $t$ from $\Gamma$.

A graph is said to be finite if its edge set is finite, even if every vertex
has even degree, locally finite if every vertex has finite degree, and
connected if any two vertices are joined by a trail. A connected component in
$\Gamma$ is a connected subgraph of $\Gamma$ which is maximal for the subgraph
relation, and the vertex set of a connected graph is a metric space with the
trail-length distance, denoted $d_{\Gamma}$.

##  3\. The proof

###  3.1. Some considerations

In this subsection we introduce some convenient terminology and prove an
useful lemma.

The following notion will be useful to define infinite trails from finite
trails. Let $t:\mathbb{\llbracket}a,b\mathbb{\rrbracket}\to\Gamma$ and
$s:\mathbb{\llbracket}c,d\mathbb{\rrbracket}\to\Gamma$ be edge disjoint
trails. If the final vertex of $t$ is also the initial vertex of $s$, the
concatenation of $s$ at the right of $t$ is the trail whose domain is
$\mathbb{\llbracket}a,b+d-c\mathbb{\rrbracket}$, whose restriction of $r$ to
$\mathbb{\llbracket}a,b\mathbb{\rrbracket}$ equals $t$, and the restriction of
$r$ to $\mathbb{\llbracket}b,b+d-c\mathbb{\rrbracket}$ follows the same path
as $s$, but with the domain shifted. If the final vertex of $s$ coincides with
the initial vertex of $t$, we define the concatenation of $s$ at the left of
$t$ as the trail whose domain is
$\mathbb{\llbracket}a-(d-c),b\mathbb{\rrbracket}$, which on
$\mathbb{\llbracket}a-(d-c),a\mathbb{\rrbracket}$ follows the route of $s$ but
with the domain shifted, and on $\mathbb{\llbracket}a,b\mathbb{\rrbracket}$
follows the route of $t$.

We say that a trail extends $t$ if its restriction to the domain of $t$ is
equal to $t$. For example, if we concatenate a trail at the right or left of
$t$, we obtain a trail which extends $t$. Finally we define the inverse of
$t$, denoted $-t$, as the trail with domain
$\mathbb{\llbracket}-b,-a\mathbb{\rrbracket}$ and which visits the vertices
and edges visited by $t$ in but in reverse order.

We now proceed to prove the following result. This will be used repeteadly
along our proofs.

######  Lemma 3.1.

Let $\Gamma$ be a connected graph and let $t$ be a trail on $\Gamma$ such that
every vertex different from the initial or final vertex of $t$ has even or
infinite degree in $\Gamma$. Then there is a trail which visits all vertices
and edges visited by $t$, with the same initial and final vertices as $t$, and
whose remotion from $\Gamma$ leaves no finite connected component.

###### Proof.

In this proof we only need to do some parity verifications in order to apply
Euler’s theorem. The only care required is because we do not assume $\Gamma$
to be locally finite.

Let $\Gamma^{\prime}$ be the subgraph of $\Gamma$ induced by the edges visited
by $t$ and the edges in finite connected components of $\Gamma-t$. We will
prove that this graph admits an Eulerian trail from $t(0)$ to $t(b)$. It is
clear that $\Gamma^{\prime}$ is connected. To see that it is finite, note that
each vertex visited by $t$ belongs to at most one connected component of
$\Gamma-t$, and there is at most one finite connected component of $\Gamma-t$
for each vertex visited by $t$.

We now show that all vertices in $\Gamma^{\prime}$ different from $t(0),t(b)$
have even degree in $\Gamma^{\prime}$, that $t(0),t(b)$ have both even degree
in $\Gamma^{\prime}$ if they are equal, and that $t(0),t(b)$ have both odd
degree in $\Gamma^{\prime}$ if they are different. This proves the claim by
Euler’s theorem.

Let $v$ be a vertex in $\Gamma^{\prime}$ not visited by $t$, so its degree in
$\Gamma$ equals its degree in $\Gamma^{\prime}$. The fact that
$\Gamma^{\prime}$ is finite shows $\deg_{\Gamma}v$ is finite, and then the
hypothesis on $\Gamma$ implies that $v$ has even degree in $\Gamma^{\prime}$.
Now let $v$ be a vertex visited by $t$, but different from $t(0)$ and $t(b)$.
We verify that $\deg_{\Gamma^{\prime}}(v)$ is finite and even. Indeed, observe
that there is at most one (possibly empty) connected component of $\Gamma-t$
containing $v$. If this connected component is infinite, then there is no
finite connected component of $\Gamma-t$ containing $v$, and
$\deg_{\Gamma^{\prime}}(v)=\deg_{t}(v)$, a finite and even number. If this
connected component is finite then $\deg_{\Gamma}(v)$ is finite and then even.
From this it follows that $\deg_{\Gamma^{\prime}}(v)$ is also even.

We now adress $t(0)$ and $t(b)$. If our claim on the degrees of $t(0)$ and
$t(b)$ fails, then $\Gamma^{\prime}$ would have exactly one vertex with odd
degree. This contradicts the handshakes lemma, which asserts that $\sum_{v\in
V(\Gamma^{\prime})}\deg_{\Gamma^{\prime}}(v)$ equals $2|E(\Gamma^{\prime})|$,
and in particular is an even number. This concludes the proof. ∎

###  3.2. The case of one-sided infinite trails

In this subsection we prove Theorem 1.1. We have verified in the introduction
that the conditions $\mathscr{E}_{1}$ are necessary for a graph to admit a
one-sided infinite Eulerian trail, so we need to prove that they are
sufficient.

Let us define what is a distinguished vertex in a graph $\Gamma$ satisfying
$\mathscr{E}_{1}$. If $\Gamma$ has one vertex with odd degree, then this is
its only distinguished vertex. If $\Gamma$ has no vertex with odd degree then
all vertices with infinite degree are distinguished. Now we can give the
following definition, which will be the base of our proof.

######  Definition 3.2.

Let $\Gamma$ be a graph satisfying $\mathscr{E}_{1}$. We say that a trail $t$
is right-extensible in $\Gamma$ if the following conditions hold.

  1. (1)

$\Gamma-t$ is connected.

  2. (2)

The initial vertex of $t$ is distinguished in $\Gamma$.

  3. (3)

There is an edge $e$ incident to the final vertex of $t$ which was not visited
by $t$.

A simple case by case analysis considering finitude and parity of the vertex
degrees shows the following result.

######  Lemma 3.3.

Let $\Gamma$ be a graph satisfying $\mathscr{E}_{1}$. If $t$ is a right-
extensible trail in $\Gamma$ then $\Gamma-t$ also satisfies $\mathscr{E}_{1}$,
and the final vertex of $t$ is a distinguished vertex in $\Gamma-t$.

Now the idea for proving Theorem 1.1 is very simple. In order to extend a
trail $t$ we remove it from $\Gamma$, and find a right-extensible trail in
$\Gamma-t$ whose initial vertex is the final vertex of $t$. Then we
concatenate these two trails and obtain a right-extensible trail in $\Gamma$
which extends $t$. This process can be iterated to obtain a one-sided Eulerian
infinite trail. To ensure that the obtained infinite trail is indeed Eulerian,
we will show that at each step of the process we can obtain a trail that
visits any edge of our choice. This is the purpose of the following two
lemmas.

######  Lemma 3.4.

Let $\Gamma$ be a graph satisfying $\mathscr{E}_{1}$, and let $v$ be a
distinguished vertex in $\Gamma$. Then for any edge $e$ there is a right-
extensible trail on $\Gamma$ which starts at $v$ and visits $e$.

###### Proof.

As $\Gamma$ is connected, there is a trail
$s:\mathbb{\llbracket}0,c\mathbb{\rrbracket}\to\Gamma$ with $s(0)=v$ and which
visits $e$. We apply Lemma 3.1 to the trail $s$, and obtain a trail
$t:\mathbb{\llbracket}0,b\mathbb{\rrbracket}\to\Gamma$ with the same initial
vertex and which visits $e$, but whose deletion leaves a connected graph.

We claim that $t$ is right-extensible. Indeed, the first and second conditions
hold by our choice of $t$. For the third condition we separate the cases where
$t$ is closed or not. Recall that that the degree of $t(0)$ in $\Gamma$ is odd
or infinite because it is a distinguished vertex. If $t$ is a closed trail
then $\deg_{t}(t(0))$ is even, it follows that $t(b)$ has edges in $\Gamma$
not visited by $t$. On the other hand if $t$ is not a closed trail then
$\deg_{t}(t(b))$ is odd while $\deg_{\Gamma}(t(b))$ is even or infinite, it
also follows that $t(b)$ has edges in $\Gamma$ not visited by $t$. ∎

######  Lemma 3.5.

Let $\Gamma$ be a graph satisfying $\mathscr{E}_{1}$. Then for any right-
extensible trail $t$ and edge $e$ there is a right-extensible trail which
extends $t$ and visits $e$.

###### Proof.

By Lemma 3.3 the graph $\Gamma-t$ satisfies $\mathscr{E}_{1}$ and contains the
final vertex of $t$ as a distinguished vertex. Now by Lemma 3.4 the graph
$\Gamma-t$ admits a right-extensible trail
$s:\mathbb{\llbracket}0,c\mathbb{\rrbracket}\to\Gamma-t$ which starts at the
final vertex of $t$, and which visits $e$. Thus the trail
$t^{\prime}:\mathbb{\llbracket}0,b+c\mathbb{\rrbracket}\to\Gamma$ obtained by
concatenating $s$ at the right of $t$ is right-extensible in $\Gamma$, visits
$e$, and extends $t$. This concludes the argument. ∎

Now the proof of the following result is a straightforward application of the
previous results.

######  Proposition 3.6.

Let $\Gamma$ be a graph satisfying $\mathscr{E}_{1}$. Then it admits a one-
sided infinite Eulerian trail.

###### Proof.

Let $(e_{n})_{n\in\mathbb{N}}$ be a numbering of the edges in $E(\Gamma)$. We
define a sequence of right-extensible trails $(t_{n})_{n\in\mathbb{N}}$ as
follows. The first of them, $t_{0}$, is a right-extensible trail whose initial
vertex is some distinguished vertex, and which visits $e_{0}$. This trail
exists by Lemma 3.4. We now define $t_{n},n\geq 1$ in the following recursive
manner. Assume that $t_{n-1}$ has been defined, and define $t_{n}$ as a right-
extensible trail which extends $t_{n-1}$ and visits $e_{n}$. The existence of
$t_{n}$ is guaranteed by Lemma 3.3. Finally we define a one-sided infinite
Eulerian trail $T:\mathbb{\llbracket}\mathbb{N}\mathbb{\rrbracket}\to\Gamma$
by setting $T(x)=t_{n}(x)$ and $T(\\{x,x+1\\})=t_{n}(\\{x,x+1\\})$, for $n$
big enough. ∎

Indeed, we have proved something a bit stronger.

######  Corollary 3.7.

Let $\Gamma$ be a graph satisfying $\mathscr{E}_{1}$. Then a trail on $\Gamma$
is right-extensible if and only if it can be extended to a one-sided infinite
Eulerian trail. Moreover, a vertex is distinguished in $\Gamma$ if and only if
it is the initial vertex of a one-sided infinite Eulerian trail on $\Gamma$.

###### Proof.

We prove the first claim. If $t$ is right-extensible, then we can replace
$t_{0}$ in the proof of Proposition 3.6 by an extension of $t$. This is
possible by Lemma 3.4, and proves the forward implication. For the remaining
implication observe that the restriction of a one-sided infinite Eulerian
trail to $\mathbb{\llbracket}0,b\mathbb{\rrbracket}$ for $b\in\mathbb{N}$ is
right-extensible.

For the second claim, note that the forward implication was implicit in the
proof of Proposition 3.6. For the remaining implication, it is clear that the
initial vertex $v$ of a one-sided infinite Eulerian trail must have odd or
infinite degree, and that no vertex different from $v$ can have odd degree in
$\Gamma$. ∎

This concludes our proof of Theorem 1.1. We now proceed to consider two-sided
infinite trails.

###  3.3. The case of two-sided infinite trails

In this subsection we prove Theorem 1.2. We start by verifying that the
conditions $\mathbf{\mathscr{E}}_{2}$ are necessary for a graph to admit a
two-sided infinite Eulerian trail.

######  Proposition 3.8.

The conditions $\mathbf{\mathscr{E}}_{2}$ are necessary for a graph to admit a
two-sided infinite Eulerian trail.

###### Proof.

By the discussion in the introduction it only remains to verify the third
condition in $\mathbf{\mathscr{E}}_{2}$, for which we proceed by
contradiction. Assume that $\Gamma$ is a graph which admits a two-sided
infinite Eulerian trail $T$ and $E$ is a finite set of edges which induces an
even subgraph such that $\Gamma-E$ has two infinite conected components.

Let $u$ and $v$ be the first and last vertex in $\Gamma[E]$ visited by $T$,
which must be different. Now let $F$ be the set of edges visited by $T$ after
$u$ but before $v$, so $E\subset F$. Observe that a restriction of $T$ is an
Eulerian trail in $\Gamma[F]$ from $u$ to $v$. As $\Gamma[E]$ is an even
graph, we obtain that $\Gamma[F]-E$ is a graph where $u$ and $v$ have odd
degree, and the remaining vertices have even degree. Moreover $\Gamma[F]-E$
can not be connected, otherwise $\Gamma-E$ would be connected. Thus a
connected component of $\Gamma[F]-E$ containing $u$ is a finite and connected
graph containing exactly one vertex with odd degree. This is a contradiction
by the handshakes lemma. ∎

We now proceed to prove the sufficiency of the conditions
$\mathbf{\mathscr{E}}_{2}$. The proof is based in the following notion.

######  Definition 3.9.

Let $\Gamma$ be a graph satisfying $\mathbf{\mathscr{E}}_{2}$. We say that a
trail $t$ is bi-extensible in $\Gamma$ if the following conditions hold.

  1. (1)

$\Gamma-t$ has no finite connected components.

  2. (2)

There is an edge $e$ incident to the final vertex of $t$ which was not visited
by $t$.

  3. (3)

There is an edge $f\neq e$ incident to the initial vertex of $t$ which was not
visited by $t$.

If no confusion arises, we simply say that a trail is bi-extensible. Observe
that when $\Gamma$ has one end, the first condition in the definition simply
means that $\Gamma-t$ is connected.

By the third condition in $\mathbf{\mathscr{E}}_{2}$, the remotion of a closed
trail from a graph satisfying $\mathbf{\mathscr{E}}_{2}$ leaves a connected
graph. Indeed we have the following result, whose proof is simply a
verification of the conditions in $\mathbf{\mathscr{E}}_{2}$.

######  Lemma 3.10.

Let $\Gamma$ be a graph satisfying $\mathbf{\mathscr{E}}_{2}$. A closed trail
$t$ is bi-extensible if and only if $\Gamma-t$ also satisfies
$\mathbf{\mathscr{E}}_{2}$.

We now prove some simple facts about bi-extensible trails. As we did with
right-extensible trails before, we will show that bi-extensible trails exist,
and can be extended to larger bi-extensible trails.

######  Lemma 3.11.

Let $\Gamma$ be a graph satisfying $\mathbf{\mathscr{E}}_{2}$. Then for any
vertex $v$ and edge $e$ there is a bi-extensible trail which visits $v$ and
$e$.

###### Proof.

By connectedness of $\Gamma$ there is a trail
$t:\mathbb{\llbracket}0,b\mathbb{\rrbracket}\to\Gamma$ which visits both $v$
and $e$. By Lemma 3.1 we can assume that the remotion of this trail leaves no
finite connected component in $\Gamma$. We now consider two cases.

If $t$ is not closed then we claim that it is bi-extensible. Indeed, as $t(0)$
and $t(b)$ have odd degree in $t$, they have incident edges $e$ and $f$ not
visited by $t$, and thus both vertices lie in $\Gamma-t$. Now observe that we
can take $e\neq f$, as otherwise the graph $\Gamma-t$ would be forced to have
a finite connected component, contradicting our choice of $t$.

If $t$ is a closed trail, then we can reparametrize it in order to obtain a
bi-extensible trail as follows. As $\Gamma$ is connected $t$ visits a vertex
$u$ which lies in $\Gamma-t$. Now as the degree of $u$ in $\Gamma-t$ is even,
there are at least two different edges in $\Gamma-t$ which are incident to
$u$. This holds even if some edge incident to $u$ in $\Gamma-t$ is a loop. We
simply reparametrize $t$ so that its initial and final vertex is $u$, and the
trail we obtain is bi-extensible. ∎

######  Lemma 3.12.

Let $\Gamma$ be a graph satisfying $\mathbf{\mathscr{E}}_{2}$. Then for any
bi-extensible trail $t$ and edge $e$ there is a bi-extensible trail which
extends $t$ and visits $e$. Moreover, we can choose this extension of $t$ so
that its domain strictly extends the domain of $t$ in both directions.

###### Proof.

We claim that given $t$ and $e$ as in the statement there is a bi-extensible
trail $s$ which extends $t$, visits $e$, and its domain strictly extends the
domain of $t$ in one direction, which we can choose. This claim implies the
one in the statement as we can apply it twice. We proceed now to prove this
claim, for which we consider three cases. Some of these cases are represented
in Figure 2 on page 2.

In the first case $t:\mathbb{\llbracket}a,b\mathbb{\rrbracket}\to\Gamma$ is a
closed trail. Then $\Gamma-t$ is connected by the third condition in
$\mathbf{\mathscr{E}}_{2}$, and the graph $\Gamma-t$ satisfies
$\mathbf{\mathscr{E}}_{2}$ by Lemma 3.10. We apply Lemma 3.11 to the graph
$\Gamma-t$ to obtain a trail
$t_{1}:\mathbb{\llbracket}a_{1},b_{1}\mathbb{\rrbracket}\to\Gamma-t$ which
visits the vertex $t(a)=t(b)$, the edge $e$, and is bi-extensible on
$\Gamma-t$. We split $t_{1}$ in two trails as follows. Let
$c_{1}\in[a_{1},b_{1}]$ be such that $t_{1}(c_{1})=t(a)$, and define $l_{1}$
and $r_{1}$ as the restrictions of $t_{1}$ to
$\mathbb{\llbracket}a_{1},c_{1}\mathbb{\rrbracket}$ and
$\mathbb{\llbracket}c_{1},b_{1}\mathbb{\rrbracket}$, respectively. Finally,
define the trail $s$ by concatenating $l_{1}$ to the left of $t$, and $r_{1}$
to its right. The fact that $t_{1}$ is bi-extensible on $\Gamma-t$ ensures
that $s$ is bi-extensible on $\Gamma$, and it visits $e$ by construction. An
alternative way to define the trail $s$ is by concatenating $-r_{1}$ at the
left of $t$, and $-l_{1}$ to its right.

Observe that $c_{1}$ could be equal to $a_{1}$ or $b_{1}$, in this situation
the domain of $s$ extends that of $t$ only in one direction. We can choose
this direction with the two possible definitions of $s$. Thus we have proved
our claim in the case where $t$ is a closed trail and $\Gamma-t$ is connected.

In the second case $t:\mathbb{\llbracket}a,b\mathbb{\rrbracket}\to\Gamma$ is
not closed and $\Gamma-t$ is connected. We show that we can extend $t$ to a
bi-extensible closed trail $s$. This suffices as the new trail $s$ belongs to
the first case. As $\Gamma-t$ is connected we can take a trail
$t_{2}:\mathbb{\llbracket}a_{2},b_{2}\mathbb{\rrbracket}\to\Gamma-t$ whose
initial vertex is $t(a)$ and whose final vertex is $t(b)$. By Lemma 3.1 we can
assume that $(\Gamma-t)-t_{2}$ has no finite connected components. We now
split $t_{2}$ as follows. Let $c_{2}\in[a_{2},b_{2}]$ be such that
$t_{2}(c_{2})$ lies in $(\Gamma-t)-t_{2}$, that is, $t_{2}(c_{2})$ is a vertex
with incident edges not visited by $t_{2}$. By the parity of the vertex
degrees there must be at least two such edges. Then define $l_{2}$ and $r_{2}$
as the restrictions of $t_{2}$ to
$\mathbb{\llbracket}a_{2},c_{2}\mathbb{\rrbracket}$ and
$\mathbb{\llbracket}c_{2},b_{2}\mathbb{\rrbracket}$, respectively. Note that
the final vertex of $-l_{2}$ is $t(a)$, and the initial vertex of $-r_{2}$ is
$t(b)$. Define $s$ by concatenating $-l_{2}$ to the left of $t$, and then
$-r_{2}$ to its right. By our choice of $t_{2}$ and $c_{2}$, $s$ is a bi-
extensible closed trail which extends $t$. This concludes the second case.

In the third case, $t$ is not closed and $\Gamma-t$ is not connected. Thus
$\Gamma-t$ has exactly two infinite connected components, each of which
satisfies $\mathscr{E}_{1}$ and where the initial and final vertex of $t$ are
distinguished. We simply apply Lemma 3.4 on each of these components and then
concatenate to extend $t$ as desired.

Figure 2.  A representation of some of the cases in the proof. At the left is
the first case, where $t$ is shown in black and $t_{1}$ in gray. In the
middle, the subcase of the first case in which $c_{1}$ equals $b_{1}$. At the
right the second case, where $t$ is shown in black and $t_{2}$ in gray.

∎

Now the proof of the following result is a straightforward application of the
previous results.

######  Proposition 3.13.

Let $\Gamma$ be a graph satisfying $\mathbf{\mathscr{E}}_{2}$. Then it admits
a two-sided infinite Eulerian trail.

###### Proof.

Let $(e_{n})_{n\in\mathbb{N}}$ be a numbering of the edges in $E(\Gamma)$. We
define a sequence of bi-extensible trails $(t_{n})_{n\in\mathbb{N}}$ as
follows. The first of them, $t_{0}$, is a bi-extensible trail which visits
$e_{0}$. This trail exists by Lemma 3.11. Now define $t_{n},n\geq 1$ in the
following recursive manner. Assume that $t_{n-1}$ has been defined, and define
$t_{n}$ as a bi-extensible trail which extends $t_{n-1}$, whose domain
strictly extends that of $t_{n-1}$ in both directions, and which visits
$e_{n}$. The existence of $t_{n}$ is guaranteed by Lemma 3.12. Finally we
define a two-sided infinite Eulerian trail
$T:\mathbb{\llbracket}\mathbb{Z}\mathbb{\rrbracket}\to\Gamma$ by setting
$T(x)=t_{n}(x)$ and $T(\\{x,x+1\\})=t_{n}(\\{x,x+1\\})$, for $n$ big enough. ∎

As in the one-sided case, we have proved the following stronger result. The
proof is identical to that of Corollary 3.7.

######  Corollary 3.14.

Let $\Gamma$ be a graph satisfying $\mathbf{\mathscr{E}}_{2}$. Then a trail is
bi-extensible if and only if it can be extended to a two-sided infinite
Eulerian trail.

##  4\. The computability of the proof

In this section we prove Theorem 1.3, for which we first introduce some
computability notions for infinite graphs. A computable graph is a graph
$\Gamma$ whose edge and vertex sets are endowed with an indexing or numbering
by decidable sets of natural numbers $I$ and $J$, $E(\Gamma)=(e_{i})_{i\in
I}$, $V(\Gamma)=(v_{j})_{j\in J}$, such that the incidence relation between
edges and pairs of vertices is decidable. That is, the following is a
decidable set:

$\\{(i,j,k)\mid e_{i}\text{ joins }v_{j}\text{ and
}v_{k}\\}\subset\mathbb{N}^{3}.$

In a computable graph, a one-sided (resp. two-sided) infinite trail is
computable if the corresponding edge and vertex functions are computable when
translated to natural numbers.

The hypothesis of computable graph is rather weak. Without further hypothesis,
the decidability of the incidence relation only allows us to enumerate set of
neighbors of a vertex. We will need the stronger notion of highly computable
graph, which is a computable graph for which the vertex degree function
$\deg_{\Gamma}:V(\Gamma)\to\mathbb{N}$ is computable.

In a highly computable graph we can compute finite subgraphs of any desired
size. More precisely, given a vertex $v$ and a distance $n\in\mathbb{N}$, we
can compute the finite subgraph induced by all edges incident to a vertex $u$
with $d(u,v)\leq n$.

Some of the algorithms which we encounter are uniform in the graph, in the
sense that the algorithm does not depend on the graph. A formal way to refer
to this fact is with the following notion. We call a description of a highly
computable graph the four-tuple of the algorithms which decide membership in
$I$, $J$, the relation of incidence between edges and pairs of vertices, and
the vertex degree function.

We proceed now to prove some lemmas about highly computable graphs.

######  Lemma 4.1.

There is an algorithm which on input the description of a highly computable
graph $\Gamma$ and a finite set of edges $E$ in $\Gamma$, halts if and only if
$\Gamma-E$ has some finite connected component.

###### Proof.

Fix a vertex $v$, and for each $n$ compute the set of edges $E_{n}$ which are
incident to a vertex at distance at most $n$ from $v$ in the graph $\Gamma$.
Then compute the induced subgraph $\Gamma_{n}=\Gamma[E_{n}]-E$. If $\Gamma-E$
has a finite connected component, we can algorithmically detect this in
$\Gamma_{n}$ for some $n$, and stop the procedure. ∎

######  Lemma 4.2.

There is an algorithm which on input the description of a highly computable
graph with one end $\Gamma$ and a finite set of edges $E$ in $\Gamma$, decides
whether $\Gamma-E$ is connected.

###### Proof.

By Lemma 4.1, it suffices to exhibit an algorithm which on input a description
of $\Gamma$ and $E$ as in the statement, halts if and only if $\Gamma-E$ has
no connected component.

Given $E$ and $\Gamma$, let $V$ be the set of vertices in $\Gamma-E$ which are
incident to some edge in $E$. Observe that the set $V$ can be computed upon
$\Gamma$ and $E$. Now define a relation $R_{E}\subset V\times V$ as follows. A
pair of vertices $(u,v)$ lies in $R_{E}$ if and only if they lie in the same
connected component in $\Gamma-E$. Note that a pair $(u,v)$ lies in $R$ if and
only if there is a trail which connects them in $\Gamma-E$, and thus such
trail can be found by just performing an exhaustive search.

In summary, there is an algorithm which given the graph $\Gamma$ and the set
of edges $E$, computes the set $V$, and enumerates the set $R_{E}$. In order
to conclude that $\Gamma-E$ is connected, we just run this algorithm, and stop
the procedure once we notice that $R_{E}$ has exactly one equivalence class. ∎

######  Lemma 4.3.

There is an algorithm which on input the description of a highly computable
graph with two ends $\Gamma$, and a finite set of edges such that $\Gamma-E$
has two infinite connected decides whether $\Gamma-E$ has some finite
connected component.

###### Proof.

By Lemma 4.1, it suffices to exhibit an algorithm which given $\Gamma$ and $E$
as in the statement, halts if and only if $\Gamma-E$ has no finite connected
component. Indeed, we can repeat the process described in Lemma 4.2, with the
only difference that we must stop the algorithm once we have found two
equivalence classes in the associated relation instead of one. ∎

Using these lemmas, the proof of the following result is straightforward.

######  Proposition 4.4.

Let $\Gamma$ be a highly computable graph.

  1. (1)

If $\Gamma$ satisfies $\mathscr{E}_{1}$, then it is algorithmically decidable
whether a trail is right-extensible.

  2. (2)

If $\Gamma$ satisfies $\mathbf{\mathscr{E}}_{2}$ and has one end, then it is
algorithmically decidable whether a trail is bi-extensible.

  3. (3)

If $\Gamma$ satisfies $\mathbf{\mathscr{E}}_{2}$ and has two ends, then it is
algorithmically decidable whether a trail whose remotion leaves two infinite
connected components is bi-extensible.

###### Proof.

Observe that the second and third conditions in Definition 3.2 and Definition
3.9 are clearly decidable, so it only remains to verify the decidability first
one. For one ended graphs satisfying $\mathscr{E}_{1}$ and
$\mathbf{\mathscr{E}}_{2}$ this follows from Lemma 4.2, while the claim for
two ended graphs follows from Lemma 4.3. ∎

We are now in position to prove Theorem 1.3, where we just have to review the
procedures described in the previous section. Observe that a highly computable
graph satisfying $\mathscr{E}_{1}$ or $\mathbf{\mathscr{E}}_{2}$ must have
infinitely many vertices and edges, and we can assume that they are indexed as
$E(\Gamma)=(e_{i})_{i\in\mathbb{N}}$ and $V(\Gamma)=(v_{i})_{i\in\mathbb{N}}$.

###### Proof of Theorem 1.3.

We start with the $\mathscr{E}_{1}$ case. A procedure to obtain a one-sided
infinite trail on $\Gamma$ was described in Proposition 3.6, where we defined
a sequence of trails $(t_{n})_{n\in\mathbb{N}}$. We now justify that this
procedure can be performed computably. Indeed, in order to compute the trail
$t_{n}$ for some $n$ we just need to do an exhaustive search among all trails
in an ordered manner. The conditions imposed on $t_{n}$ are decidable by
Proposition 4.4, and its existence is guaranteed by Lemma 3.5. We have
sketched an algorithm which on input $n$ outputs $t_{n}$, and this makes the
associated infinite trail $T$ computable.

We now consider the $\mathbf{\mathscr{E}}_{2}$ case, which has only a minor
difference. In the proof of Proposition 3.13 we defined a sequence of bi-
extensible trails $(t_{n})_{n\in\mathbb{N}}$. If $\Gamma$ has two ends, then
we choose $t_{0}$ to be a trail where $\Gamma-t_{0}$ has two infinite
connected components333This trail clearly exists. For example, we can take a
restriction of a bi-infinite Eulerian trail on $\Gamma$, which exists as
$\Gamma$ satisfies $\mathbf{\mathscr{E}}_{2}$. Alternatively, $t_{0}$ can be
constructed by iterating Lemma 3.1.. Thus regardless the number of ends of
$\Gamma$, it is decidable whether a trail extending $t_{0}$ is bi-extensible.
The remaining of the argument is the same as in the case $\mathscr{E}_{1}$. ∎

Let us now make a remark on uniformity. For one ended graphs satisfying
$\mathscr{E}_{1}$ or $\mathbf{\mathscr{E}}_{2}$, we have shown that the
corresponding infinite trail can be computed upon a description of the graph.
An alternative way to say this is that the infinite trail can be computed by
an algorithm which takes as input finite subgraphs of $\Gamma$, that is, it
uses the graph as oracle. For two ended graphs satisfying
$\mathbf{\mathscr{E}}_{2},$ however, we also need to hard code the trail
$t_{0}$ from the previous proof inside the algorithm associated to $\Gamma$,
and we do not know whether such trail can be computed upon a description of
the graph. This is related to the following more basic question which we were
not able to answer.

######  Question 4.5.

Let $\Gamma$ be a highly computable graph with two ends. Is it possible to
decide, given a finite set of edges $E$, whether $\Gamma-E$ has two infinite
connected components?

We end this section with a very simple example which shows that in Theorem 1.3
we can not relax the hypothesis from highly computable to computable.

######  Example 4.6.

We construct a computable graph satisfying $\mathbf{\mathscr{E}}_{2}$ but
which does not admit a computable two-sided infinite Eulerian trail. Let
$P\subset\mathbb{Z}$ be a computably enumerable and undecidable set, and let
$\Gamma$ be the graph whose vertex set is $\mathbb{Z}\times\\{0\\}\cup
P\times\\{1\\}$, and with edge relation as follows. For each $z\in\mathbb{Z}$,
there is one edge joining $(z,0)$ and $(z+1,0)$. Moreover for each $z\in P$,
there are two edges joining $(z,0)$ and $(z,1)$. Thus the vertex degree of
$(z,0)$ is 4 when $z\in P$, and 2 if $z\not\in P$.

A computable numbering for $\Gamma$ is obtained by taking a computable
bijection $\mathbb{N}\to\mathbb{N}\times\\{0,1\\}$, and then composing with
two computable and surjective functions $\mathbb{N}\to\mathbb{Z}$,
$\mathbb{N}\to P$. We claim that this computable graph does not admit a
computable two-sided infinite Eulerian trail. It suffices to note that for
each $z\in P$, such a trail must visit the vertices $(z,0)$, then $(z,1)$, and
then $(z,0)$ consecutively. Thus such a trail would allow us to compute the
vertex degree function. This in turn would allow us to decide membership in
$P$, and this is a contradiction.

## Acknowledgements

The author whish to thank his advisors Cristóbal Rojas and Sebastián Barbieri
by their support during the preparation of this paper. This research was
partially supported by ANID 21201185 doctorado nacional, 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.

## References

  * [1] Nicanor Carrasco-Vargas.  The geometric subgroup membership problem, March 2023.  arXiv:2303.14820 [math].
  * [2] Reinhard Diestel and Daniela Kühn.  Graph-theoretical versus topological ends of graphs.  Journal of Combinatorial Theory. Series B, 87(1):197–206, 2003\.
  * [3] Pál Erdős, T. Grünwald, and E. Weiszfeld.  On Eulerian lines in infinite graphs.  Matematikai és Fizikai Lapok, 43:129–140, 1936.
  * [4] Hans Freudenthal.  Über die Enden diskreter Räume und Gruppen.  Commentarii Mathematici Helvetici, 17:1–38, 1945.
  * [5] Heinz Hopf.  Enden offener Räume und unendliche diskontinuierliche Gruppen.  Commentarii Mathematici Helvetici, 16:81–100, 1944.
  * [6] Carl G. jun. Jockusch and Robert I. Soare.  $\Pi ^0_1$ classes and degrees of theories.  Transactions of the American Mathematical Society, 173:33–56, 1972\.
  * [7] Alfred B. Manaster and Joseph G. Rosenstein.  Effective matchmaking (recursion theoretic aspects of a theorem of Philip Hall).  Proceedings of the London Mathematical Society. Third Series, 25:615–654, 1972.
  * [8] J. B. Remmel.  Graph colorings and recursively bounded \\(\Pi ^ 0_ 1\\)-classes.  Annals of Pure and Applied Logic, 32:185–194, 1986.
  * [9] Brandon Seward.  Burnside’s problem, spanning trees and tilings.  Geometry & Topology, 18(1):179–210, 2014.
  * [10] E. Specker.  Ramsey’s theorem does not hold in recursive set theory, 1971.  Published: Logic Colloqu. ’69, Proc. Summer School Colloqu. math. Logic, Manchester 1969, 439-442 (1971).