In the mathematics of infinite graphs, an end of an undirected 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 ${\displaystyle v_{0},v_{1},v_{2},\dots }$ 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 ${\displaystyle r_{0}}$ and ${\displaystyle r_{1}}$ are equivalent if there is a ray ${\displaystyle r_{2}}$ (which may equal one of the two given rays) that contains infinitely many of the vertices in each of ${\displaystyle r_{0}}$ and ${\displaystyle r_{1}}$. 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 ${\displaystyle r_{0}}$ and ${\displaystyle r_{1}}$ are equivalent if there is no finite set ${\displaystyle X}$ of vertices that separates infinitely many vertices of ${\displaystyle r_{0}}$ from infinitely many vertices of ${\displaystyle r_{1}}$. This is equivalent to Halin's definition: if the ray ${\displaystyle r_{2}}$ from Halin's definition exists, then any separator must contain infinitely many points of ${\displaystyle r_{2}}$ and therefore cannot be finite, and conversely if ${\displaystyle r_{2}}$ does not exist then a path that alternates between ${\displaystyle r_{0}}$ and ${\displaystyle r_{1}}$ 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 ${\displaystyle G}$. In the game in question, a robber is trying to evade a set of policemen by moving from vertex to vertex along the edges of ${\displaystyle G}$. The police have helicopters and therefore do not need to follow the edges; however the robber can see the police coming and can choose where to move next before the helicopters land. A haven is a function ${\displaystyle \beta }$ that maps each set ${\displaystyle X}$ of police locations to one of the connected components of the subgraph formed by deleting ${\displaystyle X}$; 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 ${\displaystyle X}$ is a subset of ${\displaystyle Y}$, and both ${\displaystyle X}$ and ${\displaystyle Y}$ are valid sets of locations for the given set of police, then ${\displaystyle \beta (X)}$ must be a superset of ${\displaystyle \beta (Y)}$. A haven has order ${\displaystyle k}$ if the collection of police locations for which it provides an escape strategy includes all subsets of fewer than ${\displaystyle k}$ vertices in the graph; in particular, it has order ${\displaystyle \aleph _{0}}$ (the smallest aleph number) if it maps every finite subset ${\displaystyle X}$ of vertices to a component of ${\displaystyle G\setminus X}$. Every ray in ${\displaystyle G}$ corresponds to a haven of order ${\displaystyle \aleph _{0}}$, namely, the function ${\displaystyle \beta }$; that maps every finite set ${\displaystyle X}$ to the unique component of ${\displaystyle G\setminus X}$ that contains infinitely many vertices of the ray. Conversely, every haven of order ${\displaystyle \aleph _{0}}$ can be defined in this way by a ray. Two rays are equivalent if and only if they define the same haven, so the ends of a graph are in one-to-one correspondence with its havens of order ${\displaystyle \aleph _{0}}$.

If the infinite graph ${\displaystyle G}$ is itself a ray, then it has infinitely many ray subgraphs, one starting from each vertex of ${\displaystyle G}$. However, all of these rays are equivalent to each other, so ${\displaystyle G}$ only has one end.

If ${\displaystyle G}$ is a forest (that is, a graph with no finite cycles), then the intersection of any two rays is either a finite path or a ray; two rays are equivalent if their intersection is a ray. If a base vertex is chosen in each connected component of ${\displaystyle G}$, then each end of ${\displaystyle G}$ contains a unique ray starting from one of the base vertices, so the ends may be placed in one-to-one correspondence with these canonical rays. Every countable graph ${\displaystyle G}$ has a spanning forest with the same set of ends as ${\displaystyle G}$. However, there exist uncountably infinite graphs with only one end in which every spanning tree has infinitely many ends.

If ${\displaystyle G}$ is an infinite grid graph, then it has many rays, and arbitrarily large sets of vertex-disjoint rays. However, it has only one end. 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).