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 in terms of equivalence classes of infinite paths. A in an infinite graph is a semi-infinite simple path; that is, it is an infinite sequence of vertices 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 and are equivalent if there is a ray (which may equal one of the two given rays) that contains infinitely many of the vertices in each of and . 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. An alternative definition of the same equivalence relation has also been used: two rays and are equivalent if there is no finite set of vertices that separates infinitely many vertices of from infinitely many vertices of . This is equivalent to Halin's definition: if the ray from Halin's definition exists, then any separator must contain infinitely many points of and therefore cannot be finite, and conversely if does not exist then a path that alternates as many times as possible between and must form the desired finite separator.