A ray, in an infinite graph, is a semi-infinite path: a connected infinite subgraph in which one vertex has degree one and the rest have degree two. defined two rays r0 and r1 to be equivalent if there exists a ray r2 that includes infinitely many vertices from each of them. This is an equivalence relation, and its equivalence classes are called the ends of the graph. defined a thick end of a graph to be an end that contains infinitely many rays that are pairwise disjoint from each other. An example of a graph with a thick end is provided by the hexagonal tiling of the Euclidean plane. Its vertices and edges form an infinite cubicplanar graph, which contains many rays. For example, some of its rays form Hamiltonian paths that spiral out from a central starting vertex and cover all the vertices of the graph. One of these spiraling rays can be used as the ray r2 in the definition of equivalence of rays, showing that every two rays are equivalent and that this graph has a single end. There also exist infinite sets of rays that are all disjoint from each other, for instance the sets of rays that use only two of the six directions that a path can follow within the tiling. Because it has infinitely many pairwise disjoint rays, all equivalent to each other, this graph has a thick end. Halin's theorem states that this example is universal: every graph with a thick end contains as a subgraph either this graph itself, or a graph formed from it by modifying it in simple ways, by subdividing some of its edges into finite paths. The subgraph of this form can be chosen so that its rays belong to the given thick end. Conversely, whenever an infinite graph contains a subdivision of the hexagonal tiling, it must have a thick end, namely the end that contains all of the rays that are subgraphs of this subdivision.
Analogues for finite graphs
As part of their work on graph minors leading to the Robertson–Seymour theorem and the graph structure theorem, Neil Robertson and Paul Seymour proved that a family F of finite graphs has unbounded treewidth if and only if the minors of graphs in F include arbitrarily largesquare grid graphs, or equivalently subgraphs of the hexagonal tiling formed by intersecting it with arbitrarily large disks. Although the precise relation between treewidth and grid minor size remains elusive, this result became a cornerstone in the theory of bidimensionality, a characterization of certain graph parameters that have particularly efficient fixed-parameter tractable algorithms and polynomial-time approximation schemes. For finite graphs, the treewidth is always one less than the maximum order of a haven, where a haven describes a certain type of strategy for a robber to escapethe police in a pursuit-evasion game played on the graph, and the order of the haven gives the number of police needed to catch a robber using this strategy. Thus, the relation between treewidth and grid minors can be restated: in a family of finite graphs, the order of the havens is unbounded if and only if the size of the grid minors is unbounded. For infinite graphs, the equivalence between treewidth and haven order is no longer true, but instead havens are intimately connected to ends: the ends of a graph are in one-to-one correspondence with the havens of order ℵ0. It is not always true that an infinite graph has a haven of infinite order if and only if it has a grid minor of infinite size, but Halin's theorem provides an extra condition under which it becomes true.
