End (graph theory)

Ends may be formalized mathematically as equivalence classes of infinite paths, as havens describing strategies for pursuit–evasion games on the graph, or (in the case of locally finite graphs) as topological ends of topological spaces associated with the graph.

Ends of graphs were defined by Rudolf Halin (1964) in terms of equivalence classes of infinite paths.

This is an equivalence relation: each ray is equivalent to itself, the definition is symmetric with regard to the ordering of the two rays, and it can be shown to be transitive.

[2] An alternative definition of the same equivalence relation has also been used: two rays

from Halin's definition exists, then any separator must contain infinitely many points of

until no more alternations are possible must form the desired finite separator.

Ends also have a more concrete characterization in terms of havens, functions that describe evasion strategies for pursuit–evasion games on a graph

of police locations to one of the connected components of the subgraph formed by deleting

; a robber can evade the police by moving in each round of the game to a vertex within this component.

Havens must satisfy a consistency property (corresponding to the requirement that the robber cannot move through vertices on which police have already landed): if

if the collection of police locations for which it provides an escape strategy includes all subsets of fewer than

(the smallest aleph number) if it maps every finite subset

If a base vertex is chosen in each connected component of

This may be seen most easily using the characterization of ends in terms of havens: the removal of any finite set of vertices leaves exactly one infinite connected component, so there is only one haven (the one that maps each finite set to the unique infinite connected component).

In point-set topology, there is a concept of an end that is similar to, but not quite the same as, the concept of an end in graph theory, dating back much earlier to Freudenthal (1931).

If a topological space can be covered by a nested sequence of compact sets

may be made into a topological space in two different but related ways: In either case, every finite subgraph of

Thus, a graph may be covered by a nested sequence of compact sets if and only if it is locally finite, having a finite number of edges at every vertex.

is connected and locally finite, then it has a compact cover in which the set

This space can be represented as a metric space if and only if the graph has a normal spanning tree, a rooted spanning tree such that each graph edge connects an ancestor-descendant pair.

If a normal spanning tree exists, it has the same set of ends as the given graph: each end of the graph must contain exactly one infinite path in the tree.

is defined to be a free end if there is a finite set

has infinitely many ends, then either there exists an end that is not free, or there exists an infinite family of rays that share a common starting vertex and are otherwise disjoint from each other.

Halin's grid theorem characterizes the graphs that contain thick ends: they are exactly the graphs that have a subdivision of the hexagonal tiling as a subgraph.

[10] Mohar (1991) defines a connected locally finite graph to be "almost symmetric" if there exist a vertex

As he shows, for every connected locally finite almost-symmetric graph, the number of ends is either at most two or uncountable; if it is uncountable, the ends have the topology of a Cantor set.

Additionally, Mohar shows that the number of ends controls the Cheeger constant

ranges over all finite nonempty sets of vertices of the graph and where

In the case of a finitely generated group, the ends of the group are defined to be the ends of the Cayley graph for the finite set of generators; this definition is invariant under the choice of generators, in the sense that if two different finite set of generators are chosen, the ends of the two Cayley graphs are in one-to-one correspondence with each other.

The free group on one generator has a doubly infinite path as its Cayley graph, with two ends.