{'fraction_non_alphanumeric': 0.03472184160043847, 'fraction_numerical': 0.008824335434365579, 'mean_word_length': 3.601639344262295, 'pattern_counts': {'":': 0, '<': 1, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 3, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
End compactifications in non-locally-finite graphs

There are different definitions of ends in non-locally-finite graphs which are all equivalent in the locally finite case. We prove the compactness of the end-topology that is based on the principle of removing finite sets of vertices and give a proof of the compactness of the end-topology that is constructed by the principle of removing finite sets of edges. For the latter case there exists already a proof in \cite{cartwright93martin}, which only works on graphs with countably infinite vertex sets and in contrast to which we do not use the Theorem of Tychonoff. We also construct a new topology of ends that arises from the principle of removing sets of vertices with finite diameter and give applications that underline the advantages of this new definition.


Introduction
Ends of graphs can be seen as the directions along which sequences of vertices can tend to infinity. Freudenthal [4] was the first who considered ends on a class of topological spaces, which we nowadays call locally finite graphs. Usually ends are defined as equivalence classes of rays. Although one can find various literature on ends of locally finite graphs, for an introduction to this topic see [10] or [8], there does not even exist a standard definition of ends in the non-locally-finite case. Halin [5] calls two rays equivalent, when both have infinitely many vertices in common with a third ray. We call the arising equivalence classes vertex-ends, on which the topological considerations of Polat in [11], [12] and [13] are based. Cartwright, Soardi, Woess [1], Dicks and Dunwoody [2], [3] and Stallings [14] prefer ends that are constructed by the principle of removing finite sets of edges. We call them edge-ends. For the latter approach to the subject Dunwoody has proved the existence of so-called structure trees for graphs with more than one end, which can be powerful tools in describing structures of infinite graphs with a strong action of its automorphism group [3]. An improved proof can be found in [2]. At the other hand each vertex-end is contained in an edge-end, which means that vertex-ends can describe structures that cannot be seen by using edge-ends. Cf. Example 3, Example 5 and Lemma 7. But none of these two approaches could yield convincing arguments for taking one of them as the standard. Our new construction of socalled metric ends, that is only based on the principle of distinguishing between sets of finite and sets of infinite diameters, enables us to describe structures that cannot even be seen by using vertex-ends (cf. Example 4, Example 5 and Section 8), but we do not claim to have reached the end of this discussion.
We want to see ends as points in the boundaries of the compactification of topologies on the set of vertices of a graph, first of all to obtain a concept for the convergence of sequences of vertices.
Throughout this article we will only use rather simple theorems of General Topology. For the most part we will use pure graphtheoretic arguments. We could see end compactifications in a more general topological context, but in our experience this is in most of the cases not too useful.
The edge-compactification with corresponding topology τ E , which is the compactification that arises from the definition of edge-ends, is the only one from which we can construct a Hausdorff topology τ E 2 in a natural way, cf. [1], further explanations thereto can be found at the end of Section 4. Although it is a rather weak topology, it is the concept that is used by the majority of the authors.
Into this topology we can embed the topology τ V of the vertex-compactification, the counterpart of the vertex-ends.
The proper metric topology τ P , arising from the definition of metric ends, is the strongest of the three topologies and has nearly all 'good' topological properties but when we want it to be compact we have to add two artificial extra points (improper ends) and the resulting metric topology τ M is not even T 0 although every sequence has a convergent subsequence with a unique limit. The reason for that is that there is no natural concept of local convergence in compactifications of discrete metric spaces which allows all open balls with positive real radius to be open. We can embed the other end compactifications into the proper metric topology but not into the metric compactification with its two extra points.
There do not arise any problems from these two extra points, when we want to use this topology for example to describe convergence of a transient random walk to a boundary (cf. Section 8), because the probability of the event that they occur as a limit is usually zero. The proper metric topology has furthermore some pretty topological properties concerning the study of quasi-isometries (cf. Theorem 6 and Theorem 7).
Random walks on graphs can tend to infinity along directions that cannot be described in a pure graph theoretical way without using the properties of the transition densities. It would be a subject of further researches to find homeomorphisms between graphtheoretical end compactifications and probability theoretical compactifications like the Martin compactification under corresponding preliminary restrictions to the random walk. In [1] the Martin boundary is embedded into the space of edge-ends. Figure 2 shows a synopsis of some topological properties of the end topologies that will be discussed in this article.

A simple property of non-locally-finite graphs
To give a slight impression of the properties of non-locally-finite graphs we first of all want to state a simple lemma which characterises graphs with infinite diameter. Throughout this article let X = (V X, EX) be a connected graph without loops and multiple edges. A set of vertices e is called connected, if any two vertices in e can be connected by a path in X that does not leave e. When we consider topological connectedness we will mention it explicitly if it is not clear from the context. We write e * for the complement V X\e of e and diam X for the diameter with respect to the natural graph metric d X of X. The set of all connected components of e * is denoted by C(e). For the set of those connected components in e * that have a finite diameter we write C 0 (e). A star ball is a ball K for which A ray is a sequence (x n ) n∈N of pairwise disjoint vertices such that x n ∼ x n+1 for all n. Lemma 1.

1.
A locally finite graph has infinite diameter if and only if it contains a ray. 2. The diameter of a non-locally-finite graph is infinite if and only if it contains a ray with infinite diameter or a star ball.
Example 1. Let {P n | n ∈ N, diam P n = n} be a set of disjoint paths. By joining together the initial vertices of these paths we obtain a graph X with a vertex x of infinite degree. The diameter of X is infinite. There does not exist a ray with infinite diameter but for any natural radius r the ball B(x, r) is a star ball. See Figure 1.
Proof of Lemma 1. The first statement is well known. To prove the second part of the lemma we have to show that there exists a ray with infinite diameter in any graph X that does not contain a star ball. If there is no star ball in X then the complement of any vertex x in X must contain a connected component e 0 with infinite diameter. At least one of the components in the ball K(x, 1) * which are contained in e 0 must have infinite diameter. Otherwise K(x, 1) would be a star ball. We call this component e 1 . By induction we obtain a strictly decreasing sequence (e r ) r∈N of components of K(x, r) * with infinite diameter. In the proof of Lemma 3 we will see that there must exist a ray that has infinitely many vertices in common with every set e r . Since the ray is not contained in any ball it must have infinite diameter.

The construction of vertex-and edge-topology
We define the vertex-boundary θe as the set of vertices in e * which are adjacent to a vertex in e. Iθe := θe * is called inner vertex-boundary of e. The edge-boundary δe is defined as the set of edges connecting vertices in e with vertices in e * . We call a nonempty set of vertices e vertex-or edge-cut if θe or δe are finite, respectively.
Note that every edge-cut is also a vertex-cut. The reversal of this statement is not true in the general case, but in locally finite graphs vertex-cut and edge-cut are equivalent terms. It will turn out that this is the reason why the two topologies we are interested in are identical in the locally finite case.
A ray lies in a set of vertices e or is contained in e, if e contains all but finitely many elements of the ray. Sometimes we will use the terms contain and lie at the same time in the above sense as well as in the sense of set theoretic inclusion. A set of vertices e separates two rays, if one of them lies in e and the other lies in e * .
To rays are called vertex-equivalent or edge-equivalent if they cannot be separated by vertex-or edge-cuts, respectively. It is easy to see that these relations are equivalence relations. Their equivalence classes are called vertex-and edge-ends of X, respectively. As every edge-cut is a vertex-cut, all vertex-ends are subsets of edge-ends. An end lies in a set of vertices e or is contained in e, if all of its rays lie in e. The set of vertex-ends that lie in e is denoted by Ω V e, the set of edge-ends in e by Ω E e. We write Ω V/E X instead of Ω V/E V X. Indeed, a vertex-end or edge-end ω lies in a vertex-cut or edge-cut e if and only if one of its rays lies in e, respectively. ω lies either in e or in e * . We say that a finite set of vertices e separates two ends, if they lie in different connected components of e * .
Example 2. The two sided infinite 'ladder graph' has two ends. In locally finite graphs we do not have to distinguish between different types of ends.  Proof. For two sets e 1 ∪ Ω V e 1 and e 2 ∪ Ω V e 2 in B V X we have e 1 ∩ e 2 is a vertex-cut and Ω V e 1 ∩ Ω V e 2 the set of ends whose rays are completely contained in e 1 and e 2 from some index onwards. Thus Ω V e 1 ∩ Ω V e 2 = Ω V (e 1 ∩ e 2 ), and finally We define the set B E X analogously, for which the proof of Lemma 2 can be copied word by word. Hence B V X and B E X are bases of topological spaces (V X ∪ Ω V X,τ V X) and (V X ∪ Ω E X,τ E X), whose topologies τ V X and τ E X are called vertextopology and edge-topology, respectively.

Compactness of the vertex-and edge-topologies
Lemma 3. If there is a vertex z for every strictly decreasing sequence (e n ) n∈N of connected edge-or vertex-cuts, such that K(z, n) is a subset of e * n , then there exists a ray L, which has infinitely many vertices in common with all cuts e n . In other words: The end of L lies in all cuts e n .
Proof. As e 1 is connected and a superior set of e 2 any vertex x 1 in Iθe 1 can be connected by a path π 1 of vertices in e 1 \e 2 with a vertex x 2 in Iθe 2 . By induction we get a path π n such that the initial vertex of π n is adjacent to the last vertex of π n−1 and π n is contained in e n \e n+1 for every natural n greater than one. The union L of these paths must have finite intersection with every ball with center z (eq. every bounded subset of V X). Thus L is infinite and therefore it constitutes a ray. The corresponding end lies in all cuts e n . Proof. Under the given preliminaries there exists a vertex x in θe with infinite degree, which is adjacent to infinitely many connected components of e containing elements of ξ. Every element f ∪ Ω V f of the base B V X which contains x must contain almost all of these components, since the vertex-boundary of e is finite. The same holds for every neighbourhood of x. Thus x is an accumulation point of ξ.
is the only vertex-cut, then every element of V X ∪ Ω E X is an accumulation point of the sequence. Otherwise let z be a vertex in the complement of a vertex-cut e, in which lie infinitely many elements of ξ. If the sequence has no accumulation point in θe, then by Lemma 4 there exists a connected component e 0 of e, such that infinitely many elements of ξ lie in e 0 .
In the case that ξ has no accumulation point in θe 0 , we construct a connected vertex-cut e 1 , that is a subset of e 0 \Iθe 0 and contains infinitely many elements of ξ: For a vertex y in θe 0 with infinite degree, which is no accumulation point of ξ, there exists a vertex-cut f (y), that contains y and for which f (y) ∪ Ω V f (y) contains only finitely many elements of ξ. Almost all vertices in Iθe 0 , that are neighbours of y, lie in f (y). Thus e 0 \f (y) is a cut, such that infinitely many elements of the sequence ξ lie in it. This and the finiteness of θe 0 imply that e A 1 := e 0 \ {f (y) | y ∈ θe 0 , deg(y) = ∞} is a vertex-cut, which is a subset of e 0 and contains almost all elements of Iθe 0 . Thus e B 1 := e A 1 \Iθe 0 is also a vertex-cut. It is a subset of e 0 \Iθe 0 . If ξ has no accumulation point in θe B 1 , once more by Lemma 3, there exists a connected component e 1 of e B 1 , that has again the properties requested before.
By induction we obtain a strictly decreasing sequence (e n ) n∈N of connected vertex-cuts, in all of which lie infinitely many elements of the sequence ξ. Since e n+1 is a subset of e n \Iθe n and the vertex z lies in the complement of e 0 we have K(z, n) ∩ e n = ∅ and thus n∈N e n = ∅.
Following Lemma 3 we obtain a ray L, whose end ω lies in every cut e n . Every neighbourhood U of ω contains a base element f ∪ Ω V f with ω ∈ Ω V f , for which θf is a subset of one of the balls K(z, n). This implies, that almost all cuts e n and thus infinitely many elements of the sequence ξ lie in any neighbourhood of ω.
Proof. We may assume that an open cover U consists of base elements. Given a set e ∪ Ω V e of the cover, we choose a vertex z in e. Since θe is finite there exists a finite subcover U 1 of e ∪ θe in U. The set e 1 of vertices in U 1 is a vertex-cut. Every ray in e 1 must lie in one of those vertex-cuts f for which f ∪ Ω V f is an element of the cover U 1 . The same holds for any end containing this ray and therefore By induction we obtain a sequence of vertex-cuts (e n ) n∈N and a corresponding finite subcover U n of U, such that K(z, n) is a subset of e n . In other words: For an end ω and a vertex z we define d U (ω, z), the distance of ω to z with respect to the cover U, as the minimal radius r for which there exists a base element f ∪Ω V f in U such that θf is a subset of K(z, r). Note that this radius exists for all vertexends. Let f ∪ Ω V f be a base element in U. If the vertex boundary of f is contained in e n , then for an x in θe n ∩ f all connected components of (e n ∪ θe n ) * which are adjacent to x are completely contained in f . Let W n denote the set of elements of U whose vertex-boundaries are subsets of e n . We now choose a finite subcover V n of W n which covers θe n ∩ W n . Now V n covers all ends ω with d U (ω, z) ≤ n and the union n∈N U n ∪ V n is a countable covering of both V X and Ω V X which meets the statement of the lemma.
Proof. A sequentially compact Lindelöf space is compact. Thus we can conclude from Lemma 5 and Lemma 6, that (V X ∪ Ω V X,τ V X) is compact. It remains to show that at least one of two elements x and y of V X ∪ Ω V X has an open environment, in which the other element is not contained. We distinguish: 1. One of the two elements is a vertex. If x is a vertex, then (V X\{x} ∪ Ω V X) is the requested neighbourhood of y. 2. x and y are ends. In the complement of a finite set of vertices that separates x and y there exist two disjoint base elements, of which one contains the end x and the other y.
, whose restriction on V X is the identity. Proof.
We define the f -image of an end in Ω V X as the end in Ω E X that contains it. The preimage of every base element of the edge-topology is open in the vertextopology.
Proof. The statement is a consequence of Theorem 1 and Lemma 7.
Example 3. We connect two adjacent vertices x 1 and x 2 with each vertex of two disjoint rays L 1 and L 2 , respectively. The resulting graph X 1 has two vertex-and two edge-ends, see Figure 4a. When we take away the edge {x 1 , x 2 } and identify the vertices x 1 and x 2 we obtain a graph X 2 in which L 1 and L 2 are edge-equivalent but not vertex-equivalent. In other words, there exist two vertex-ends but only one edge-end, see Figure 4b. L 1 and L 2 , and therefore their corresponding vertex-ends lie in every neighbourhood of x in the vertex-topology. Thus is not a T 1 -space. In the edge-topology the edge-end of X 2 and the vertex x cannot even be separated in the sense of the T 0 -axiom. In the graph X 1 the same holds for the edge-end of L 1 and L 2 and the vertices x 1 and x 2 , respectively.  As shown in Example 3 there may exist vertices with infinite degree, whose neighbourhoods in the edge-topology all contain a fixed edge-end. To avoid such complications and to obtain better properties of separation the edge equivalence can be extended to the set of rays and vertices with infinite degree. In other words, vertices with infinite degree are considered as degenerated rays. They also can define new ends, so-called improper vertices. We then obtain edge topologies τ E 2 of the second type which are compact, totally disconnected and normal, either by defining {x} as open sets a priori for all vertices x, see [1] or by considering vertices x with infinite degree as degenerated rays only and not as vertices (cf. [7]). In the first case the edge-topology is a compactification of the discrete topology on V X. The compactness of these modified topologies can be deduced easily from Theorem 2. Hence e E is an edge-cut and e V is a vertex-cut. The same argument holds for (V X ∪ Ω V X)\c V and therefore e * V is a vertex-cut, too. Thus e V is an edge-cut.
An end in ε E or ε V must lie in e E or e V , respectively, because c E and c V are open. On the other hand every end lying in e E or e V must be an element of ε E or ε V , respectively. Otherwise the complements of c E and c V would not be open.

Metric ends
Sometimes theorems for locally finite graphs can be generalized for non-locallyfinite graphs or their proofs can be simplified by replacing arguments that use the finiteness of sets of vertices by arguments of finite diameters (cf. [7]). At the other hand there even exist rather simple structures whose ramifications can neither be captured by the vertex-nor by the edge-topology (cf. Example 4 and Example 5). This motivates a new definition of ends in non-locally-finite graphs, which is only based on the natural graph metric.
A metric cut is a set of vertices with a vertex-boundary of finite diameter. A ray whose infinite subsequences have all infinite diameters is called metric ray. Two metric rays are metrically equivalent, if they cannot be separated by metric cuts. Metrical equivalence is an equivalence relation on the set of metric rays of a graph. We call its equivalence classes proper metric ends. A proper metric end lies in a set of vertices e if all of its rays lie in e.
We denote the set of proper metric ends that lie in e by Ω P e and write Ω P X instead of Ω P V X.
Lemma 8. For any graph X, the set B P X := {e ∪ Ω P e | e ⊂ V X and diam θe < ∞} is closed under finite intersection.
The proof can be copied word by word from Lemma 2.
We now can define the proper metric end topology τ P X as the topology on V X ∪ Ω P X which is generated by B P X.
Theorem 4. The proper metric end topology is a totally disconnected Tychonoff topology. In the case that X is locally countably infinite it is Lindelöf and normal. If there exists a vertex with infinite degree it is not paracompact.
Proof. For any closed set F not containing some point x we can find a neighbourhood A of x, which is element of the base and contained in the complement of F . As the base elements in B P X are open and closed the indicator function on A is continuous. Thus the proper metric end topology is T 3 1 2 or completely regular. Zero-dimensionality is also an immediate consequence of the fact that elements of the base are open and closed. It is easy to see that this topology is Hausdorff which now implies that it is Tychnoff and totally disconnected.
Let X be a locally countable graph. For some given vertex x let V denote the set of all base elements e ∪ Ω P e such that e is a connected component of K(x, r) * for some natural r. V is countable. Any element of an open cover U containing a proper metric end must contain an element of V. Thus we can find a countable subcover of U of the set of proper metric ends. The set of vertices is countable anyway and hence the proper metric end topology is Lindelöf. Every regular Lindelöf space is normal.
For any vertex x with infinite degree is an open cover which is not locally finite in x and therefore the proper metric end topology is not paracompact.
We do not know whether the proper metric end topology is normal in the general case.
Example 4. Let X be the graph which arises from a tree T with only vertices of infinite degree to which we add edges connecting all pairs of vertices with distance two. The proper metric topologies on X and T are homeomorphic, in contrast to the vertex-and the edge-topology on X, which are indiscrete and therefore describe no structure at all.
To motivate the definitions of the following section we remark that every sequence of vertices that has neither an accumulation point in V X (equivalently: has infinitely many identical elements) nor an accumulation point in Ω P X can be divided up into two types of subsequences: 1. Bounded sequences.
2. Sequences with no bounded subsequences for which there exists a metric cut, whose complement consists only of components that contain at most finitely many elements of the sequence.

A compactification of the proper metric end topology
We will now add two additional points to the set of metric ends and modify the proper metric topology correspondingly.
A star-cut is a metric cut e such that every union r of all but finitely many components of its complement has infinite diameter. For a star-cut e we call such a union r star-boundary of e. A set s of vertices is called a global star-set if to every star-cut e there exists a star-boundary r, such that r\s has a finite diameter.
An infinite set of vertices p is called locally complete, if it contains all but finitely many elements of every ball.
If there exists a star-cut in V X we add an element σ X called the star-end to the set of proper metric ends. Furthermore we add an element λ to the set of ends which we call the local end. The set Ω M X so obtained is called set of metric ends of X, λ X and σ X are called improper metric ends. We say that the local end lies in a set of vertices e, if it is a locally complete set. If e is a global star-set we say that the star-end lies in e. Let Ω M e denote the set of all metric ends, that lie in e.
Although the local end will be useless in locally finite graphs (equivalently: it is an isolated point, {λ X } is open), we add it to the set of ends in any way. This will help use to find homeomorphisms between end-spaces in locally and non-locallyfinite graphs.

Lemma 9. The set
s is a global star-set and p is a locally complete set,} is closed under finite intersection.
We call the topology τ M X on V X ∪ Ω M X, which is generated by B M X, metric end topology.
Proof. Let U be an open cover of base elements. It must contain sets p ∪ Ω M p and s ∪ Ω M s such that p is a locally complete set and s is a global star-set. After removing these base elements from V X ∪ Ω M X we obtain a set A ∪ ΩA such that A ⊂ p * ∩ s * and ΩA ⊂ Ω P X\Ω P s. A is a set of vertices, that contains only finitely many elements of any ball in X. Thus A is countable and we can find a countable subcover V of V X in U. We now copy the ideas in the second part of the proof of Lemma 6 to construct a countable subset of U which covers ΩA.
Let d U (ω, z) again denote the distance of the end ω to the vertex z with respect to the cover U. As A contains no star-boundary, it has the property that for every metric cut e we can find a union u of finitely many components of e * , such that A\u has a finite diameter. Thus there are only finitely many connected components in (s ∪ K(z, n)) * for any natural number n, we can find a finite subcover V n of U covering all ends with d U (ω, z) ≤ n, that lie in ΩA. Thus is a compact topological space. All limits of convergent sequences are unique. For a convergent sequence ξ with α = lim ξ exactly one of the following cases must hold: 1. The limit α is a vertex. All elements of the sequence are equal to α from an index on. 2. From some index onwards the elements of the sequence ξ are the local end or they are vertices lying in some ball such that at the most finitely many vertices are identical. In this case ξ converges to the local end λ X . 3. In the complement of any ball exactly one component contains all but finitely many elements of the sequence ξ. There exists exactly one proper metric end lying in all these components, which is the limit α. 4. There exists a vertex x and a radius r such that for any natural n the ball K(z, r+n) is a star-cut, whose star-boundaries contain all but finitely many of those elements of the sequence, that do not equal the star-end, but contain only finitely many of them in each of their connected components. The sequence converges to the star-end σ X .
Proof. To show that every sequence in V X ∪ Ω M X has an accumulation point we can assume that it contains an infinite partial sequence ξ consisting of pairwise different elements. Otherwise the existence of an accumulation point is immediate. If ξ contains a bounded subsequence of vertices, the local end is an accumulation point. In the other case we choose a vertex x and distinguish between two cases.
1. For every natural n there exists a sequence (e n ) n∈N of components of K(x, n) * such that e n contains infinitely many elements of the sequence ξ and is a superset of e n+1 . Following the idea of Lemma 3 we now can construct a metric ray, that lies in all cuts e n . Its end is an accumulation point of ξ. 2. There exists a ball K(x, n) such that only finitely many elements of ξ lie in every component of K(x, n) * . Let s∪Ω M s be a base element that contains the star-end σ X , which means that s must be a global star-set. By the definition of a global star-set there exists a star-annulus r of K(x, n) such that r\s has a finite diameter. The set r ∪ Ω M r must contain all but finitely many elements of ξ, but as ξ contains no bounded subsequence, only finitely many elements of the sequence ξ lie in r\s. Now s ∪ Ω M s must contain all but finitely many elements of ξ, which means that σ X in an accumulation point of ξ.
We have shown that (V X ∪ Ω M X,τ M X) is sequentially compact. By Lemma 10 it is also a Lindelöf space and hence it is compact. The other statements of Theorem 5 now follow easily by the above considerations.
Example 5. Let K N denote the complete graph with vertex-set N, see Figure 5a. We take two graphs K N and K (2) N that are isomorphic to K N and connect each vertex with adjacent vertices x 1 and x 2 , respectively ( Figure 5b). As in Example 3 we take away the edge (x 1 , x 2 ) from the graph in Figure 5b, identify x 1 and x 2 to a vertex x. Then we connect each vertex in K N with x as shown in Figure 5c. In Figure 5d we take a sequence (K

Figure 5d
7. Metric ends and quasi-isometries Definition 1. Two graphs X and Y are called quasi-isometric with respect to the functions φ : V X → V Y and ψ : V Y → V X if there exist constants a, b, c and d such that for all vertices x, x 1 and x 2 in V X and vertices y, y 1 and y 2 in V Y , the following conditions hold We call φ and ψ quasi-inverse to each other.
For general metric spaces the definition of quasi-isometries allows further additive constants in the Axioms (Q1) and (Q2). In case the positive values of the metric are greater than some positive real number these additive constants are useless.
Quasi-isometries may change structures as long as the differences can be bounded uniformly. In other words we could say that they preserve the global structure of graphs when we consider graphs as discrete metric spaces only.
Without proof we remark that quasi-isometry is an equivalence relation on the family of all graphs.
Example 6. The graphs in Example 3, the ladder graph (Example 2) and the graph in Example 5, Figure 4d, as well as the tree T and the graph X in Example 4 are quasi-isometric.
For all constants r the Cayley graphs X of the free group with respect to the generating system A r in Section 8 are quasi-isometric to each other.
Replacing every edge in a graph X by a path with a length smaller or equal some constant we obtain a graph which is quasi-isometric to X.
Lemma 11. Let φ : V X → V Y be a quasi-isometry and A a subset of V X, then Let ψ be a quasi-inverse to φ. If diam X A is infinite, then, by (Q3), this also holds for diam X ψφ(A). Now has no upper bound.
Corollary 1. The pre-image of a metric cut or a global star-set set under a quasiisometry is a metric cut or a global star-set, respectively.
We now want to extend the concept of quasi-isometry to the set of proper metric ends.
Theorem 6. To every quasi-isometry φ : V X → V Y there exists a unique exten- Φ is continuous and 3. Φ| ΩPX is a homeomorphism of Ω P X and Ω P Y with respect to the corresponding relative topologies.
Proof. By connecting the φ-images of adjacent vertices of a metric ray L in X with geodesic paths with lengths, that are smaller or equal a, we obtain a path P in Y . Its diameter is infinite by Lemma 11. If it had infinite subset M with finite diameter, we also could find infinitely many elements in M that lie in φ(L), contradicting Lemma 11 and the assumption that L is a metric ray. As a graph is locally finite if and only if every bounded set of vertices is finite, P is a locally finite subgraph of Y . Lemma 1 implies that it must contain a ray which we denote withφ(L). By the above consideration it is also a metric ray in Y . Thusφ maps metric rays in X onto metric rays in Y .
Let L 1 and L 2 be metric equivalent rays in X. Ifφ(L 1 ) andφ(L 2 ) were not metrically equivalent, we could find disjoint metric cuts f 1 and f 2 , such thatφ(L 1 ) lies in f 1 andφ(L 2 ) lies in f 2 . Again by Lemma 10, φ −1 (f 1 ) ∩ φ −1 (f 2 ) must have a finite diameter and hence the rays L 1 and L 2 cannot lie in both cuts f 1 and f 2 in contradiction to the assumption that they are metrically equivalent. Thus we can say that metric equivalence is an invariance underφ on sets of metric rays. Now for every end ω in Ω P X we define Φ(ω) as the unique end in Ω P Y which contains theφ-images of the elements of ω and set Φ(x) = φ(x) for every vertex x.
By the above invariance of the metric equivalence and the construction ofφ we obtain Φ(Ω P e) ⊂ Ω P Φ(e) for every metric cut e in X, and therefore by Corollary 1 Now let ω be a proper metric end in Φ −1 (Ω P f ). Then of course Φ(ω) ∈ Ω P f . If ω did not lie in Φ −1 (f ) then there would exist infinitely many vertices x in a ray L of ω which are not elements of Φ −1 (f ). Their φ-images would not be elements of f ,φ(L) would not lie in f and Φ(ω) would not element of Ω P f . Hence For every base element f ∪ Ω P f in B P Y we obtain and Φ is continuous.
To prove the third property of Φ, it now suffices to show that the restriction Φ| ΩPX is a bijection of the sets of ends in X and Y . To a given end ε in Ω P Y we can find a decreasing sequence (f n ) n∈N of connected metric cuts in Y such that n∈N f n = ∅ and n∈N Ω P f n = ε. Now we choose an increasing sequence (K(z, r n )) n∈N of concentric balls in X such that θΦ −1 (f n ) is contained in K(z, r n ). To every natural n there exists a connected component e n of K(z, r n ) * which contains all but finitely many vertices of the Φ-preimage of a ray L of ε. Copying the idea of Lemma 3 we can find a metric ray R that lies in all cuts e n . The end ω of R is mapped onto ε under Φ. Thus Φ is surjective.
Let ε 1 and ε 2 be two different ends of the graph Y and f 1 and f 2 two disjoint metric cuts such that ε 1 lies in f 1 and ε 2 lies in f 2 . Now Φ −1 (Ω P f 1 ) and Φ −1 (Ω P f 2 ) must be disjoint too, and therefore Φ is injective.
To complete the proof of the theorem, it remains to show that Φ is the unique extension of φ with the requested properties. We assume that there exists another extensionΦ which has these three properties but does not equal Φ. Let ω be an end in X and Φ(ω) = ε 1 andΦ(ω) = ε 2 for two different ends ε 1 and ε 2 in Y . Now we choose again two disjoint metric cuts f 1 and f 2 such that ε 1 lies in f 1 and ε 2 lies in f 2 . As Φ −1 (f 1 ) = φ −1 (f 1 ) andΦ −1 (f 2 ) = φ −1 (f 2 ), the preimages Φ −1 (f 1 ) and Φ −1 (f 2 ) are disjoint metric cuts in X. We know that ω must lie in Φ −1 (f 1 ) and therefore ω must lie inΦ −1 (f 2 ) * . This implies that every open neighbourhood of ω has a nonempty intersection withΦ −1 (f 2 ) * . In other words, no open neighbourhood of ω is completely contained inΦ −1 (f 2 ∪ Ω P f 2 ) andΦ is not continuous.
For a subset A of V X ∪ Ω P X and a natural number r we define In the following sense we could call Φ a quasi-open function.
Theorem 7. For any base element e ∪ Ω P e in B P X, the set Φ(e ∪ Ω P e) + d + 1 is open in τ P Y .
Although the proof seems a little technical, its idea is simple. Quasi-isometry is a weakened form of isomorphy. The quasi-surjectivity does not ensure that the image φ(V X) covers V Y completely but says that it does not have 'holes' that are bigger than a circle with radius d.
For applications of quasi-isometries in the study of ends of graphs confer [9] and [7].

Bounded random walk on the free group
We now want to give a further example for an application of the metric end compactification concerning the random walk on the free group with countably infinitely many generators. Random walk on free groups were first introduced and studied by Kesten, [6]. Let Γ be a free group with a symmetric and countable set of generators A containing at least four elements. Every element x of Γ can be represented in a unique way by the shortest product of elements of A that equals x. The length of this product is called length of x, the length of the neutral element o is set zero. Let A r denote the set of elements with positive lengths that are less or equal some natural r. The Cayley graph X of Γ with respect to A r has vertex set V X = Γ. Two vertices x and y are adjacent if and only if x −1 y is an element of A r . X is isomorphic to a graph that arises from a regular tree T with degree |A| by connecting pairs of distinct vertices x and y with distance d T (x, y) ≤ r. Compare with Example 4.
Let µ be a probability measure on A r whose support generates the whole group Γ. Now µ defines a random walk (Z n ) n∈N on Γ with respect to the probability measure Pr on Γ N which is generated by the cylindric sets in (A r ) N together with the corresponding powers of µ.
Theorem 8. The random walk (Z n ) n∈N on the countably infinite free group Γ converges almost surely to some proper metric end in the Cayley graph X.
Proof. As the support of µ generates Γ we can choose four distinct elements a 1 , a 2 , a −1 1 and a −1 2 in A r such that µ(a 1 ) and µ(a 2 ) are positive. We define a random walk (Z n ) n∈N on the free groupΓ with generating systemÃ = {a 1 , a 2 , a −1 1 , a −1 2 } by choosing µ(a 1 ), µ(a 2 ), µ(a −1 1 ) and µ(a −1 2 ) as the probabilities for the right multiplication with the generating elements, respectively. The probability of not making a move is set 1−(µ(a 1 )+µ(a 2 )+µ(a −1 1 )+µ(a −1 2 )). We know that (Z n ) n∈N is transient (cf. for example [15]). The corresponding probability measure on the set of trajectories is denoted byPr. As the corresponding Cayley graphX is locally finite, the random walk (Z n ) n∈N does not enter any ball from an index on with probability one. ThusP r[ lim This is equivalent to the almost sure convergence of Z n to a proper metric end in the metric end topology of X. Section 2, 3 and 4 are part of the author's masters thesis [7] at the University of Salzburg under the supervision of Prof. W. Woess and the author wants to thank him for many useful suggestions. The main part of this thesis was written during a stay at Milan supported by the Italian Ministry of Foreign Affairs.