On vertex transitive graphs of infinite degree

R. Diestel, H.A. Jung, R.G. Möller

Abstract

This paper studies transitive graphs G of infinite degree and their automorphisms, with particular emphasis on the action of Aut(X) on the ends of G. Several of the most important classical results on locally finite transitive graphs and their automorphisms are proved here in full generality. In particular, it is shown that a transitive connected graph has one, two or at least continuum many ends; that an automorphism of such a graph with more than two ends is bounded if and only if it fixes every end; that these automorphisms form a locally finite subgroup of Aut(X). These results are obtained as consequences of one central theorem, which describes how the automorphisms of a transitive graph translate its finite subgraphs relative to its finite separators.

Introduction

Locally finite graphs and their automorphisms have been extensively studied in the literature. The aim of this note is to show how arbitrary transitive graphs with more than one end resemble locally finite graphs in several essential respects related to their symmetry stucture.

Our central result, Theorem 3, identifies as the key feature of a graph’s automorphism group in this respect a certain translation property concerning finite subgraphs and separations. This condition, which holds trivially in the locally finite case, is strong enough to imply (generally) the most important of the symmetry properties known for locally finite graphs, and we prove it for arbitrary transitive graphs under very weak assumptions (such as that the graph has at least two ends).

As one application, we show that a transitive connected graph with more than two ends has no free end, and hence has continuum many ends. (This is a classical theorem for locally finite graphs.) Another consequence is that for an automorphism σ of such a graph there is a finite upper bound on the distance between each vertex and its image under σ if and only if σ acts trivially on the graph’s ends. Similarly, we see that these automorphisms form a locally finite group.

We start in Section 1 by reviewing some basic facts about ends and automorphisms of graphs. Next, in Section 2, we take a look at bisections: these are finite separations of graphs into two infinite parts, which are particularly relevant for the study of automorphisms. In Section 3 we develop ideas from [6] to prove Theorem 3, together with an immediate application (Theorem 4). These two theorems are applied in Section 4 to give the results mentioned above, as well as some further corollaries.

1 Background and notation

In his seminal paper [5], Halin investigates the automorphisms of infinite graphs. He shows that the key to an understanding of the automorphisms of infinite graphs lies in their behaviour “at infinity”. Let us start by giving this phrase a precise meaning, in terms of the ends of a graph, and then review a few of the fundamental known facts about ends and automorphisms.

Let X be a connected graph with vertex set V X and edge set EX. Denote by d(−, −) the usual metric on V X. If C ⊆ V X, then the diameter of C in X is the diameter of the set C in the metric space (V X, d). Note that this differs from the diameter of the subgraph of X induced by C; in particular, the diameter of C in X cannot increase when we remove some of the vertices of C.

An end of X is an equivalence class of rays (one-way infinite paths) in X, where two rays R_{1} and R_{2} are considered equivalent if X contains infinitely many (possibly trivial) disjoint paths connecting R_{1} and R_{2}. It is easy to see that R_{1} and R_{2} are non-equivalent if and only if there exist a finite set S ⊆ V X and distinct components C_{1} and C_{2} of X −S such that R_{1} ∩ C_{1} and R_{2} ∩ C_{2} are infinite. Let ΩX denote the set of ends of X.

The boundary in X of a set C ⊆ V X, denoted by ∂C, is the set of vertices in V X \ C that are adjacent to some vertex in C. We write \overline{C} := V X \ (C ∪ ∂C). Clearly ∂\overline{C} ⊆ ∂C. If ∂C is finite, and if R_{1} and R_{2} are two rays in the same end, then R_{1} ∩ C is infinite if and only if R_{2} ∩ C is infinite. For C with finite boundary we may thus say that an end ω belongs to C if R ∩ C is infinite for some (and hence every) ray R in ω. By ΩC we denote the set of ends of X that belong to C. A finite set S ⊆ V X separates two ends if they belong to (the vertex sets of) different components of X − S. An end ω of X is called free if there is a finite set S ⊆ V X that separates ω from every other end of X.

The (full) automorphism group of a graph X is denoted by Aut(X). X is called transitive if the natural action of Aut(X) on V X is transitive. Since automorphisms preserve the equivalence of rays, Aut(X) also acts on ΩX in a natural way. We may think of ΩX as a kind of completion—or, if X is locally finite, compactification—of X (viewed as a discrete space), and of the action of an automorphism σ ∈ Aut(X) on ΩX as the action of σ at infinity. See [1] for a brief description of the standard topological setup that makes this intuition precise; for a more detailed account refer to Polat [11].

Note that a transitive connected infinite graph X contains a ray, and thus has at least one end. Indeed, if X is locally finite, this is (a special case of) an easy classical result of König; if some, and hence every, vertex of X has infinite degree, we may find a ray in X inductively.

For σ ∈ Aut(X), we say that a line (a two-way infinite path) L in X is σ-periodic if there is an integer k ≠ 0 such that σ^{k}(L) = L. Halin [5] proved that if X is connected and σ has no finite orbit, then X contains such a σ-periodic line L. (This is stated in [5] for locally finite graphs only; however, the proof given makes no use of local finiteness.) As σ^{k} induces a non-trivial shift on L (not a flip: since σ fixes no finite set, σ^{2k} does not fix a vertex), we refer to such automorphims whose orbits are all infinite as translations.

Let σ ∈ Aut(X) be a translation, and let L and k > 0 be as above. Let R^{+} ⊆ L be any ray such that σ^{k}(R^{+}) ⊆ R^{+}. The direction of σ is defined as the end of X that contains R^{+}, and is denoted by D(σ). (Halin [5] proved that this end is independent of the choice of L, R^{+} or k, so the direction of σ is well defined.) An end ω is called a direction in X if there exists a translation σ ∈ Aut(X) such that ω = D(σ).

Note that if σ is a translation, then any power of σ, in particular σ^{−1}, is also a translation. Moreover, any σ-periodic line L is also σ^{−1}-periodic, and its two ends are contained in D(σ) and D(σ^{−1}), respectively. We shall say that σ is a proper translation if D(σ) ≠ D(σ^{−1}). For example, any translation of a line is a proper translation, but the infinite grid ℤ × ℤ, which has only one end, admits no proper translation.

Note that a translation σ fixes the ends D(σ) and D(σ^{−1}). Indeed, if L is σ-periodic and σ(R^{+}) ⊆ R^{+} for a ray R^{+} ⊆ L, then σ(L) too is σ-periodic and σ(σ(R^{+})) ⊆ σ(R^{+}); since D(σ) is well defined, σ(R^{+}) must be in the same end as R^{+}, i.e. in D(σ) (and similarly for D(σ^{−1})). Halin [5] showed that σ cannot fix any other ends than D(σ) and D(σ^{−1}). (Again, Halin only states this for locally finite graphs, but his proof works equally well for graphs that are not locally finite.)

Let us define the thickness of an end ω as the maximal cardinality of a set of disjoint rays in ω; Halin [3] proved that this maximum always exists, and he denoted it by m_{1}(ω). An end ω with finite m_{1}(ω) will be called thin.

Directions of translations have the following properties:

Theorem 1 Let X be a connected graph and σ ∈ Aut(X) a translation. Then

(i) m_{1}(D(σ)) = m_{1}(D(σ^{−1})).

(ii) The translation σ is proper if and only if D(σ) is thin. (iii) There is a set of m_{1}(D(σ)) disjoint σ-periodic lines in X. (iv) Suppose σ is a proper translation, and set m := m_{1}(D(σ)). Then there exist m

disjoint σ-periodic lines L_{1}, …, L_{m} and an m-element set T ⊆ V X which separates D(σ) and D(σ^{−1}).

Note that, in (iv) above, T meets each L_{i} in exactly one vertex, and these are all the vertices of T.

Theorem 1 (in fact, a rather more elaborate version, especially of item (iv)) was proved by Halin [5, Theorem 9] for locally finite graphs. His proof carries over to graphs that are not locally finite—except for the “if” part of (ii), which follows from [7, Corollary 3.5].

2 Bisections

Let X be a connected graph, and let C_{1} ∪ F ∪ C_{2} be a partition of V X. The triple (C_{2}, F, C_{1}) will be called a bisection of X if C_{1} and C_{2} are infinite, F is finite, and ∂C_{1}, ∂C_{2} ⊆ F. Note that C_{1} and C_{2} are not required to induce connected subgraphs of X. We say that σ ∈ Aut(X) shifts the bisection (C_{2}, F, C_{1}) if σ(F ∪ C_{1}) ⊆ C_{1}; note that this implies σ^{−1}(F ∪ C_{2}) ⊆ C_{2}, i.e. σ^{−1} shifts the “inverse” bisection (C_{1}, F, C_{2}).

If (C_{2}, F, C_{1}) is a bisection of X shifted by σ, then any vertex of σ^{k}(C_{1}) has distance > k in X from any vertex of C_{2}∪F. As every vertex in C_{1} has finite distance from C_{2}∪F, this implies in particular that ⋂_{k∈ℕ} σ^{k}(C_{1}) = ∅. More generally, we have d(σ^{i}(C_{2}), σ^{j}(C_{1})) > j − i + 1 for any two integers i and j, and ⋂_{i∈I} σ^{i}(C_{1}) = ∅ as well as ⋂_{i∈I} σ^{−i}(C_{2}) = ∅ for any infinite I ⊆ ℕ.

If C is a proper subset of X with finite boundary, and σ(∂C ∪C) ⊆ C, then (\overline{C}, ∂C, C) is a bisection of X (shifted by σ). Indeed, since C ⫋ V X and X is connected, we have ∂C ≠ ∅. As C contains σ^{k}(∂C) for every k > 0, and these sets are disjoint for different k, C must be infinite. Similarly, \overline{C} is infinite, because σ^{k}(\overline{C}) contains the disjoint union of ⋃_{i=0}^{k−1} σ^{i}(∂C) (for every k ∈ ℕ).

The main result of [6] says, essentially, that any bisection (\overline{C}, ∂C, C) of a transitive graph X for which ∂C has minimal cardinality is shifted by an automorphism of X. As we have seen, this implies that X has infinite diameter. Since graphs with more than one end have bisections of the form (\overline{C}, ∂C, C), we thus have the following corollary:

Proposition 1 A transitive graph with more than one end has infinite diameter. □

(The converse of Proposition 1 is not true: the ℤ × ℤ grid is a simple one-ended transitive graph of infinite diameter.)

Note that if X is transitive and connected, then for any bisection (C_{2}, F, C_{1}), both C_{1} and C_{2} contain a ray; in particular, X has at least two ends. Indeed, if X is locally finite, then C_{1} induces only finitely many components in X −F (since every such component has a neighbour in F), and so one of these components is infinite and hence contains a ray. If X has infinite degree, then every vertex of C_{1} has infinitely many neighbours in C_{1}, and we can find a ray in C_{1} inductively. The case of C_{2} is analogous.

For a fixed graph X, we call a subset of V X connected if it induces a connected subgraph in X. The following result from [7] characterizes proper translations as the automorphisms with powers that shift bisections (\overline{C}, ∂C, C), where C is a proper connected subset:

Theorem 2 An automorphism σ of a connected graph X is a proper translation if and only if V X has a connected proper subset C such that ∂C is finite and σ^{k}(∂C ∪ C) ⊆ C for some integer k > 0.

(We remark that a proper translation does not necessarily itself shift a bisection: if V X = ℤ and EX = { xy : |x − y| ≤ 2 }, then i ↦ i + 1 is a proper translation of X shifting no bisection.)

Our next proposition provides a link between general bisections and the automorphisms shifting them.

Proposition 2 Let (C_{2}, F, C_{1}) be a bisection of a connected graph X shifted by σ ∈ Aut(X). Then σ is a proper translation whose direction D(σ) belongs to C_{1}, and whose inverse direction D(σ^{−1}) belongs to C_{2}.

Proof We first apply Theorem 2 to show that σ is a proper translation. Let S ⊆ V X be a finite connected set containing F, and let k be the diameter of S in X. Since σ^{k+1}(F) has distance ≥ k + 1 from F ∪ C_{2}, we have σ^{k+1}(S) ⊆ C_{1}, and hence σ^{k+1}(S ∪ C_{1}) ⊆ C_{1}. As S ∪ C_{1} is connected, this implies that σ^{k+1}(S ∪ C_{1}) is contained in one component induced by C_{1}, say with vertex set D. Now ∂D ⊆ S, so in particular σ^{k+1}(∂D ∪ D) ⊆ D, and so σ^{k+1} is a proper translation by Theorem 2. It is easily checked that σ, too, must then be a proper translation.

It remains to show that D(σ) belongs to C_{1} and D(σ^{−1}) belongs to C_{2}. Let L be a line in X, and k > 0 such that σ^{k} induces a non-trivial shift on L. Let us show that L has infinitely many vertices both in C_{1} and in C_{2}. Suppose not, say V := C_{2} ∩ V L is finite (and possibly empty). By definition of σ, clearly V ⊆ σ^{ik}(C_{2}) ∩ V L for every i ∈ ℕ. However, σ^{ik}(L) = L, so we also have

|V | = |σ^{ik}(V)| = |σ^{ik}(C_{2} ∩ V L)| = |σ^{ik}(C_{2}) ∩ V L| .

Hence, V = σ^{ik}(C_{2}) ∩ V L, and thus

V L \ V ⊆ σ^{ik}(F ∪ C_{1}) ⊆ σ^{ik+1}(C_{1})

for every i ∈ ℕ. This contradicts our earlier observation that ⋂_{i∈ℕ} σ^{ik}(C_{1}) = ∅. The proof that L has infinitely many vertices in C_{1} is analogous (using that σ^{ik}(C_{2}) ⊆ C_{2} for i ≤ 0, and ⋂_{i<0} σ^{ik}(C_{2}) = ∅).

We have thus shown that L has a subray in C_{1} and another in C_{2}; all that remains to be checked is that the former is in D(σ), the latter in D(σ^{−1}). Let R ⊆ L be a ray chosen so that its starting vertex lies in F but all its other vertices lie in C_{1}. Then σ^{k}(V R) ⊆ C_{1}, and hence σ^{k}(R) ⊆ R. Therefore R ∈ D(σ), so D(σ) belongs to C_{1} (and D(σ^{−1}) to C_{2}) as claimed. □

Let us note an easy consequence of these facts that will be needed later.

Proposition 3 Let ω be a thin direction of a connected graph X, and let R be a ray in ω. Then any infinite subset of V R has infinite diameter in X.

Proof Let σ be a translation of X with D(σ) = ω. By Theorem 1 (ii), σ is proper; let C ⊆ V X and k ∈ ℕ be as provided by Theorem 2. Recall that ⋂_{n∈ℕ} σ^{kn}(C) = ∅.

By Proposition 2 (or trivially, if \overline{C} is finite) the end ω = σ^{kn}(ω) belongs to σ^{kn}(C) for every n; in particular, all but finitely many vertices of R are in σ^{kn}(C). Let V be an infinite subset of V R, pick v ∈ V, and choose i ∈ ℕ so that v ∉ σ^{ki}(C). Then for each j ≥ i, any vertex of σ^{kj}(∂C ∪ C) has distance at least j − i from v. In particular, this is true for all but finitely many vertices in V. □

3 Translating finite subsets

Let X be an infinite connected graph, and let G ≤ Aut(X). We shall say that G shuffles X if the following holds:

(†) for every infinite C ⊆ V X with finite boundary, and for every finite S ⊆ V X, there is a σ ∈ G such that σ(S) ⊆ C.

If X is locally finite, then X is shuffled by any group G ≤ Aut(X) that acts transitively on V X—a fact crucial to many arguments concerning locally finite transitive graphs with at least two ends. Our main goal in this section is to show the same for transitive graphs of infinite degree.

Lemma 1 Let X be a connected graph of infinite diameter, assume that G ≤ Aut(X) acts transitively on X, and let C ⊆ V X be infinite with finite boundary. Then C satisfies (†) if and only if C has infinite diameter in X.

Proof Suppose first that the diameter of C in X is infinite, and let a finite set S ⊆ V X be given. If ∂C = ∅ then C = V X (since X is connected), and there is nothing to prove. We shall therefore assume that ∂C ≠ ∅. Since C has infinite diameter in X, and ∂C is finite, the vertices of C have unbounded distance from ∂C; choose v ∈ C so that d(v, ∂C) is greater than the diameter of S in X. Find a σ ∈ G that takes some vertex of S to v. Then σ(S) ⊆ C, as required in (†).

Suppose now that C has finite diameter in X. Take vertices v_{1} and v_{2} in X such that d(v_{1}, v_{2}) is greater than the diameter of C in X, and set S := {v_{1}, v_{2}}. Clearly no element of G can take S into C. □

Theorem 3 A connected graph X of infinite diameter is shuffled by any group G ≤ Aut(X) that acts transitively on V X.

Proof Suppose G does not shuffle X, and let

δ := min { |∂C| : C is a counterexample to (†) }.

Let us call C is a scapegoat if C is a counterexample to (†) and |∂C| = δ. Thus, by Lemma 1, a set C ⊆ V X is a scapegoat if and only if C is infinite, ∂C is finite, and C has finite diameter. We prove that there are no scapegoats.

Lemma. If C_{1} and C_{2} are scapegoats, then either C_{1} ∩ C_{2} or \overline{C_{1}} ∩ C_{2} is a scapegoat.

Proof of the Lemma. We first assume that C_{1} ∩ C_{2} is infinite and show that it is a scapegoat. Note first that

∂(C_{1} ∪ C_{2}) ⊆ (∂C_{1} ∩ \overline{C_{2}}) ∪ (∂C_{1} ∩ ∂C_{2}) ∪ (\overline{C_{1}} ∩ ∂C_{2})

and

∂(C_{1} ∩ C_{2}) ⊆ (∂C_{1} ∩ C_{2}) ∪ (∂C_{1} ∩ ∂C_{2}) ∪ (C_{1} ∩ ∂C_{2}).

(In fact, equality holds in both cases, but this will not be needed.) Combining the two inclusions, we obtain

|∂(C_{1} ∪ C_{2})| + |∂(C_{1} ∩ C_{2})| ≤ |∂C_{1} ∩ \overline{C_{2}}| + |∂C_{1} ∩ ∂C_{2}| + |\overline{C_{1}} ∩ ∂C_{2}|
+ |∂C_{1} ∩ C_{2}| + |∂C_{1} ∩ ∂C_{2}| + |C_{1} ∩ ∂C_{2}|
= |∂C_{1} ∩ C_{2}| + |∂C_{1} ∩ ∂C_{2}| + |∂C_{1} ∩ \overline{C_{2}}|
+ |C_{1} ∩ ∂C_{2}| + |∂C_{1} ∩ ∂C_{2}| + |\overline{C_{1}} ∩ ∂C_{2}|
= |∂C_{1}| + |∂C_{2}|
= 2δ

Thus, both C_{1} ∪ C_{2} and C_{1} ∩ C_{2} have finite boundary, and are therefore counterexamples to (†) by Lemma 1: like C_{1} and C_{2}, they are infinite but have finite diameter. The boundaries of C_{1} ∪ C_{2} and C_{1} ∩ C_{2} therefore have order at least δ, and hence exactly δ by the above inequality. In particular, C_{1} ∩ C_{2} is a scapegoat.

We now assume that C_{1} ∩ C_{2} is finite, and show that \overline{C_{1}} ∩ C_{2} is a scapegoat. Note first that, as earlier,

\begin{aligned}∂(\overline{C_{1}} ∩ C_{2}) & ⊆ (∂\overline{C_{1}} ∩ C_{2}) ∪ (∂\overline{C_{1}} ∩ ∂C_{2}) ∪ (\overline{C_{1}} ∩ ∂C_{2}) \\ & ⊆ (∂C_{1} ∩ C_{2}) ∪ (∂C_{1} ∩ ∂C_{2}) ∪ (\overline{C_{1}} ∩ ∂C_{2}); \end{aligned}

similarly,

∂(C_{1} ∩ \overline{C_{2}}) ⊆ (∂C_{1} ∩ \overline{C_{2}}) ∪ (∂C_{1} ∩ ∂C_{2}) ∪ (C_{1} ∩ ∂C_{2}).

Combining the two inclusions, we once more obtain

|∂(\overline{C_{1}} ∩ C_{2})| + |∂(C_{1} ∩ \overline{C_{2}})| ≤ |∂C_{1} ∩ C_{2}| + |∂C_{1} ∩ ∂C_{2}| + |∂C_{1} ∩ \overline{C_{2}}|
+ |C_{1} ∩ ∂C_{2}| + |∂C_{1} ∩ ∂C_{2}| + |\overline{C_{1}} ∩ ∂C_{2}|
= |∂C_{1}| + |∂C_{2}|
= 2δ

Thus, \overline{C_{1}} ∩ C_{2} and C_{1} ∩ \overline{C_{2}} each have finite boundary. By our assumption that C_{1} ∩ C_{2} is finite, both \overline{C_{1}} ∩ C_{2} and C_{1} ∩ \overline{C_{2}} are infinite, and they have finite diameter, because C_{2} and C_{1} have finite diameter. Thus \overline{C_{1}} ∩ C_{2} and C_{1} ∩ \overline{C_{2}} are counterexamples to (†), and hence have boundaries of order at least δ. As before, the above inequality implies that both boundaries have order exactly δ, so in particular \overline{C_{1}} ∩ C_{2} is a scapegoat. This completes the proof of the Lemma.

To complete the proof of Theorem 3, consider an arbitrary scapegoat C. Define ∂^{∗}C as the set of vertices v such that whenever D ⊆ C is a scapegoat then v ∈ ∂D. Note that ∂^{∗}C ⊆ ∂C. Furthermore, if D ⊆ C is a scapegoat, then ∂^{∗}C ⊆ ∂^{∗}D.

Now let C be any fixed scapegoat. Since |∂^{∗}D| is bounded above by δ for all scapegoats D ⊆ C, we can find a scapegoat D ⊆ C such that ∂^{∗}D = ∂^{∗}D′ for all scapegoats D′ ⊆ D.

We first prove that ∂^{∗}D = ∅. Suppose ∂^{∗}D ≠ ∅, pick a vertex v ∈ ∂^{∗}D, and choose σ ∈ G so that σ(v) ∈ D. By the Lemma, either D ∩ σ(D) or \overline{D} ∩ σ(D) is a scapegoat. Hence either

σ(v) ∈ σ(∂^{∗}D) = ∂^{∗}σ(D) ⊆ ∂^{∗}(D ∩ σ(D)) = ∂^{∗}D ⊆ ∂D,

or

σ(v) ∈ σ(∂^{∗}D) = ∂^{∗}σ(D) ⊆ ∂^{∗}(\overline{D} ∩ σ(D)) ⊆ ∂(\overline{D} ∩ σ(D)) ⊆ ∂\overline{D} ∪ \overline{D}.

Both of these contradict our assumption that σ(v) ∈ D. Thus ∂^{∗}D = ∅, as claimed.

We shall now use this fact to prove that C has infinite diameter in X; this will contradict Lemma 1. Let ∂C = {v_{1}, …, v_{k}}. Since ∂^{∗}D is empty, we can find a scapegoat D_{1} ⊆ D such that v_{1} ∉ ∂D_{1}. By definition of D, also ∂^{∗}D_{1} is empty. We may therefore repeat the argument to find a scapegoat D_{2} ⊆ D_{1} such that v_{2} ∉ ∂D_{2}, and so on. In the end we have a scapegoat D_{k} =: C_{1} such that C_{1} ∪ ∂C_{1} ⊆ C. Repeating this construction (beginning with the choice of D ⊆ C), we obtain a sequence C = C_{0} ⊇ C_{1} ⊇ C_{2} ⊇ … such that C_{i} ∪ ∂C_{i} ⊆ C_{i−1} for all i ≥ 1. Clearly ∂C_{i} has distance at least i from ∂C, so C has infinite diameter in X. □

Corollary 1 A connected graph with more than one end is shuffled by any group of automorphisms that acts transitively on its vertices.

Proof By Theorem 3 and Proposition 1. □

Corollary 2 Let X be a transitive connected graph of infinite diameter, and let C ⊆ V X be infinite with finite boundary. Then C has infinite diameter in X.

Proof By Theorem 3 and Lemma 1. □

The main result of [6], as mentioned before, says that if (C_{2}, F, C_{1}) is a bisection of X for which F has minimal cardinality (taken over all bisections of X), then any transitive group of automorphisms of X has an element σ that shifts (C_{2}, F, C_{1}). Using Theorem 3, we can now easily prove this without the cardinality restriction on F:

Theorem 4 Let X be a connected graph, and assume that G ≤ Aut(X) acts transitively on V X. Then any bisection (C_{2}, F, C_{1}) of X is shifted by a proper translation from G.

Proof Let S ⊆ V X be a finite connected set containing F. Then both S ∪ C_{1} and C_{2} ∪ S are again connected. Since X is transitive, it has at least two ends (as we observed immediately after Proposition 1). We may therefore apply Corollary 1 (with C_{1} \ S and C_{2} \S playing the role of C in (†)) to find automorphisms σ, ρ ∈ G such that σ(S) ⊆ C_{1} \S and ρ(S) ⊆ C_{2} \ S.

We now find a τ ∈ G such that τ(S ∪ C_{1}) ⊆ C_{1}. If S ∩ σ(C_{1}) = ∅, then σ(S ∪ C_{1}) is a (connected) subset of V X \ S, and hence σ(S ∪ C_{1}) ⊆ C_{1} (because σ(S ∪ C_{1}) ∩ C_{1} ≠ ∅ by definition of S). We may then put τ := σ. If S ∩ ρ(C_{2}) = ∅, then S ⊆ ρ(C_{1}) and hence S ∪ C_{1} ⊆ ρ(C_{1}), because S ∪ C_{1} is a connected subgraph of V X \ ρ(S). We may then set τ := ρ^{−1}. If neither of the above holds, then S ⊆ ρ(C_{2}) ∩ σ(C_{1}), because S is connected and avoids both ρ(S) and σ(S). Then C_{2}∪S is a connected subset of V X \σ(S) meeting σ(C_{1}), and so C_{2} ∪ S ⊆ σ(C_{1}). Similarly, S ∪ C_{1} ⊆ ρ(C_{2}). Then τ := σ^{−1}ρ^{−1} is as desired.

Proposition 2 implies that τ is a proper translation. □

4 The end structure of transitive graphs

There is a natural Hausdorff topology, called the end topology, defined on the set of ends of a graph X: a basis for this topology is given by the family

{ ΩC : C ⊆ V X with |∂C| < ∞ }.

Clearly, Aut(X) acts continuously on ΩX endowed with this topology.

The following is an easy consequence of our results from the last section.

Corollary 3 Let X be a transitive connected graph with at least two ends. Then the thin directions of X are dense in the end topology.

Proof Let U = ΩC ⫋ ΩX be a basic open set. Then (\overline{C}, ∂C, C) is a bisection. By Theorem 4 and Proposition 2 there is a proper translation σ whose direction belongs to C, i.e. with D(σ) ∈ U. By Theorem 1 (ii), D(σ) is thin. □

It is well known that a transitive locally finite connected graph with more than two ends cannot have a free end. We can now extend this to graphs that are not locally finite.

Theorem 5 If X is a transitive connected graph with more than 2 ends then X has no free ends.

Proof Suppose ω is a free end. Choose a finite connected set S ⊆ V X which separates ω from every other end of X and which, in addition, also separates some further two ends. Let C be the vertex set of a component of X − S chosen so that ω belongs to C. By Proposition 1 and Corollary 2, C has infinite diameter in X. Let k be the diameter of S in X, and pick a vertex v ∈ C with d(v, S) > k. (This can be done, because S is finite.) Choose an automorphism σ ∈ Aut(X) that maps some vertex of S to v. Then σ(S) ⊆ C. Since S separates some three ends of X pairwise, so does σ(S): we shall prove that this is impossible.

Let ω_{1} and ω_{2} be two ends other than ω. Then S separates ω from ω_{1} and from ω_{2}, so neither ω_{1} nor ω_{2} belongs to C. Choose rays R_{1} ∈ ω_{1} and R_{2} ∈ ω_{2}; since X is connected, this can be done in such a way that both these rays start in S and avoid C. Since S is connected and σ(S) ⊆ C, clearly σ(S) does not separate R_{1} from R_{2}, and hence does not separate ω_{1} from ω_{2}. □

Theorem 5 has the following consequence, whose locally finite version is a classical result on ends and automorphisms.

Corollary 4 A transitive connected infinite graph has either 1, 2 or at least 2^{ℵ_{0}} ends.

Proof As we observed in Section 1, a transitive connected graph has at least one end. By a result of Halin [3, Satz 2], a graph with at least one end but no free end has at least continuum many ends. The assertion follows by Theorem 5. □

We are now also able to generalize one of the main results of [10] to graphs that are not locally finite. Let us say that σ ∈ Aut(X) is bounded if there is a number n such that d(v, σ(v)) ≤ n for all v ∈ V X. The bounded automorphisms of X form a normal subgroup of Aut(X), which we denote by B(X). Similarly, the automorphisms of X that fix every end of X form a normal subgroup K(X): this is just the kernel of the action of Aut(X) on ΩX. In [10] it was shown that these two groups coincide for any transitive connected graph X with more than two ends, provided that X is locally finite. This latter condition (as well as the non-trivial restriction on the number of ends) is again unnecessary:

Theorem 6 An automorphism of a transitive connected graph X with at least two ends is bounded if and only if it fixes every end of X, i.e.,

B(X) = K(X).

Proof A proof for the case when X has exactly two ends is implicit in [9, Theorem 5.10]. We may therefore assume that X has more than two ends.

Let σ be a bounded automorphism of X and let ω be an end of X; we show that σ(ω) = ω. By Corollary 3 we may assume that ω is a thin direction of X. Suppose σ(ω) ≠ ω. Let S ⊆ V X be a finite set separating ω from σ(ω) in X. Let R be a ray in ω chosen so that R and σ(R) are contained in different components of X − S. Since ω is a thin direction, Proposition 3 implies that we can find vertices on R arbitarily far from S, and hence from σ(R). This contradicts our assumption that σ is bounded.

For the converse direction, we shall use Theorem 1 (iv) to show that all the K(X)- orbits of vertices of X have the same finite (size and) diameter in X, which thus bounds d(v, σ(v)) for all v ∈ V X and all σ ∈ K(X) (cf. Corollary 5 below).

Since X has several ends and hence a bisection, Aut(X) contains a proper translation τ (by Theorem 4). Let T and L_{1}, …, L_{m} be as in Theorem 1 (iv). Let C_{1} and C_{2} be the vertex sets of components of X − T chosen so that D(τ) belongs to C_{1} and D(τ^{−1}) to C_{2}. Replacing τ with a suitable positive power of τ, we may assume that L_{1}, …, L_{m} are each invariant under τ.

Each of the lines L_{i} then splits up into a ray R_{i}^{+} ∈ D(τ), which starts at the unique vertex t_{i} of L_{i} in T and has its other vertices in C_{1}, and a ray R_{i}^{−} ∈ D(τ^{−1}) whose vertices are all in C_{2}. As τ(R_{i}^{+}) ⊆ R_{i}^{+} for every i (by definition of D(τ)), we thus have τ(T) ⊆ C_{1} and τ(C_{1}) ∩ C_{1} ≠ ∅. Similarly τ^{−1}(T) ⊆ C_{2}, i.e. T ⊆ τ(C_{2}). Thus T ∩ τ(C_{1}) = ∅, and so τ(C_{1}) is a connected set that meets C_{1} but avoids T. Hence τ(C_{1}) ⊆ C_{1} (as well as τ(T) ⊆ C_{1}), i.e. τ shifts the bisection (\overline{C_{1}}, T, C_{1}). Similarly, τ^{−1} shifts the bisection (\overline{C_{2}}, T, C_{2}).

Note that, for any σ ∈ K(X), the set σ(T) separates the two ends σ(D(τ)) = D(τ) and σ(D(τ^{−1})) = D(τ^{−1}). Therefore σ(T) meets every L_{i}, and so σ(T) ⊆ V L_{1} ∪ … ∪ V L_{m} (since |σ(T)| = |T | = m). Thus, the K(X)-orbit of any vertex of T is a subset of V L_{1} ∪ … ∪ V L_{m}.

Let us show that no such K(X)-orbit can have vertices too far from T. More precisely, let us denote the diameter of T in X by k, and show that

σ(T) ⊆ V (L_{1}[τ^{−2k}(t_{1}), τ^{2k}(t_{1})] ∪ … ∪ L_{m}[τ^{−2k}(t_{m}), τ^{2k}(t_{m})])  (1)

for every σ ∈ K(X), where L_{i}[τ^{−2k}(t_{i}), τ^{2k}(t_{i})] denotes the finite subpath of L_{i} between the vertices τ^{−2k}(t_{i}) and τ^{2k}(t_{i}).

Suppose (1) fails. Then σ(T) has, for some i, a vertex v ≠ τ^{2k}(t_{i}) on τ^{2k}(R_{i}^{+}) or a vertex on τ^{−2k}(R_{i}^{−}), and therefore meets either τ^{2k}(C_{1}) or τ^{−2k}(C_{2}). We assume that σ(T) ∩ τ^{2k}(C_{1}) ≠ ∅, the other case being analogous. By definition of k, this implies that

d(T, σ(T)) > k;

recall that d(T, τ^{2k}(C_{1})) > 2k, because τ shifts the bisection (\overline{C_{1}}, T, C_{1}). Moreover,

σ(T) ⊆ C_{1};

in particular, σ(T) ∩ T = ∅.

Let us show that, in fact, σ(T ∪ C_{1}) ⊆ C_{1}, i.e. that σ, too, shifts the bisection (\overline{C_{1}}, T, C_{1}). Since d(T, σ(T)) > k, either T ∩σ(C_{1}) or T ∩σ(C_{2}) is empty. If T ∩σ(C_{2}) = ∅, then σ(C_{2} ∪ T) is a connected subset of V X \ T meeting C_{1}, so σ(C_{2} ∪ T) ⊆ C_{1}. But then σ(D(τ^{−1})), which belongs to σ(C_{2}) by definition of C_{2}, also belongs to C_{1}. This contradicts the fact that σ(D(τ^{−1})) = D(τ^{−1}), which belongs to C_{2} (and not to C_{1}). Therefore T ∩ σ(C_{1}) = ∅. Hence σ(T ∪ C_{1}) is a connected subset of V X \ T meeting C_{1}, so σ(T ∪ C_{1}) ⊆ C_{1} as claimed.

By Theorem 2, then, σ is a proper translation. But a proper translation can only fix two ends (see Section 1), so this contradicts our assumption that σ ∈ K(X) and X has more than two ends. This completes the proof of (1).

We have thus shown that the K(X)-orbit of any vertex in T is finite. Let v be a fixed vertex in T. As K(X) is normal in Aut(X) and Aut(X) is transitive, the K(X)-orbit of any vertex of X is the image under some X-automorphism of the K(X)-orbit of v, and hence has the same (finite) size and diameter in X. □

By showing, in the proof of the backward direction of Theorem 6, that all the K(X)- orbits on X are actually images of each other under automorphisms of X, we proved substantially more than was needed. In particular:

Corollary 5 If X is a transitive connected graph with more than two ends, then there is an absolute finite bound on d(v, σ(v)) which is valid uniformly for all bounded automorphisms σ of X.

(If X has only two ends, this is not true; consider, for example, shifts of a single line.)

We remark further that the (degenerate) analogue of Theorem 6 for one-ended graphs is false: the cartesian product of the dyadic tree and an infinite complete graph is an infinitely connected (and hence one-ended) transitive graph that admits unbounded automorphisms.

The proof of Theorem 6 allows us to generalize a result of Godsil et al. [2] to transitive graphs of infinite degree. A group is said to be locally finite if all its finitely generated subgroups are finite.

Corollary 6 If X is a transitive connected graph with more than two ends, then K(X) is a locally finite group.

Proof As shown in the proof of Theorem 6, all the orbits of K(X) have the same finite size. Under this condition it is proved in [2, Lemma 1] that K(X) is locally finite. □

Again, Corollary 6 fails if X has exactly two ends: then K(X) contains all the translations of X, which have infinite order in Aut(X) and hence generate infinite subgroups. However, if X has exactly two ends then it is locally finite (see Theorem 7 below), and the automorphisms of finite order in K(X) form a locally finite subgroup of Aut(X). (This was proved more generally, for any locally finite transitive graph of polynomial growth, by Godsil et al. [2].)

Our aim in this paper has been to show that transitive connected graphs with more than one end are in many ways similar to locally finite graphs. Our final result, then, which was anticipated in [9], is not too far off the mark:

Theorem 7 Transitive connected graphs X with exactly two ends are locally finite.

Proof Since X has two ends and hence has a bisection, Aut(X) contains a proper translation τ (by Theorem 4). Let T and L_{1}, …, L_{m} be as in Theorem 1 (iv). Replacing τ with a suitable power of τ, we may assume that each of the lines L_{i} is invariant under τ. Let t_{i}, R_{i}^{+}, R_{i}^{−} (for i = 1, …, m) as well as C_{1} and C_{2} be defined as in the proof of Theorem 6.

Note that, for any σ ∈ Aut(X), the set σ(T) separates the two ends of X, and must therefore consist of one vertex from each of the lines L_{1}, …, L_{m}. As X is transitive, this means that

V X = V L_{1} ∪ … ∪ V L_{m} = C_{2} ∪ T ∪ C_{1}.

In particular, (C_{2}, T, C_{1}) is a bisection shifted by τ. Hence, no vertex of T can be adjacent to any vertex in τ(C_{1}) or in τ^{−1}(C_{2}), because τ(T) (respectively, τ^{−1}(T)) separates it from those vertices. But τ(C_{1}) ∪ τ^{−1}(C_{2}) is cofinite in V X, since for each i the subray of R_{i}^{+} starting at τ(t_{i}) has all its vertices except τ(t_{i}) in τ(C_{1}), while the subray of R_{i}^{−} starting at τ^{−1}(t_{i}) has all its vertices except τ^{−1}(t_{i}) in τ^{−1}(C_{2}).

Thus any vertex in T has finite degree. As X is transitive, this shows that X is locally finite. □

References

[1] R. Diestel, The end structure of a graph, to appear in Discrete Math. 100 (1992).

[2] C.D. Godsil, W. Imrich, N. Seifter, M. E. Watkins and W. Woess, A note on bounded automorphisms of infinite graphs, Graphs and Combinatorics 5 (1989), 333–338.

[3] R. Halin, Über unendliche Wege in Graphen, Math. Ann. 157 (1964), 125–137.

[4] R. Halin, Über die Maximalzahl fremder unendlicher Wege in Graphen, Math. Nachr. 30 (1965), 63–85.

[5] R. Halin, Automorphisms and endomorphisms of infinite locally finite graphs, Abh. Math. Sem. Univ. Hamburg 39 (1973), 251–283.

[6] H. A. Jung, A note on fragments of infinite graphs, Combinatorica 1 (1981), 285–288.

[7] H. A. Jung, Some results on ends and automorphisms of graphs, to appear in: (R. Diestel, Ed.) Directions in Infinite Graph Theory and Combinatorics, Annals of Discrete Mathematics, in press.

[8] H. A. Jung and M. E. Watkins, On the connectivities of finite and infinite graphs, Mh. Math. 83 (1977), 121–131.

[9] H. A. Jung and M. E. Watkins, Fragments and automorphisms of infinite graphs, Europ. J. Combinatorics 5 (1984), 149–162.

[10] R. G. Möller, Ends of graphs, Math. Proc. Camb. Phil. Soc. 111 (1992), 255–266.

[11] N. Polat, Topological aspects of infinite graphs, in: (G. Hahn et al., Eds.) Cycles and Rays, NATO ASI Ser. C, Kluwer Academic Publishers, Dordrecht 1990.

R. Diestel, Faculty of Mathematics (SFB 343), Bielefeld University, P.O. Box 8640, D-4800 Bielefeld, Germany. H.A. Jung, Faculty of Mathematics, TU Berlin, Straße des 17. Juni 135, W-3000 Berlin 12, Germany. R.G. Möller, Mathematical Institute, 24–29 St. Giles’, GB-Oxford OX1 3LB, England.