End (graph theory)

In the mathematics of infinite graphs, an end of a graph represents, intuitively, a direction in which the graph extends to infinity. 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 may be used (via Cayley graphs) to define ends of finitely generated groups. Finitely generated infinite groups have one, two, or infinitely many ends, and the Stallings theorem about ends of groups provides a decomposition for groups with more than one end.

Ends of graphs were defined by Rudolf Halin (1964) in terms of equivalence classes of infinite paths. A ray in an infinite graph is a semi-infinite simple path; that is, it is an infinite sequence of vertices v₀, v₁, v₂, ... in which each vertex appears at most once in the sequence and each two consecutive vertices in the sequence are the two endpoints of an edge in the graph. According to Halin's definition, two rays r₀ and r₁ are equivalent if there is another ray r₂ (not necessarily different from either of the first two rays) that contains infinitely many of the vertices in each of r₀ and r₁. 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. Therefore, it partitions the set of all rays into equivalence classes, and Halin defined an end as one of these equivalence classes.

...
Wikipedia