Halin's grid theorem

In graph theory, a branch of mathematics, Halin's grid theorem states that the infinite graphs with thick ends are exactly the graphs containing subdivisions of the hexagonal tiling of the plane. It was published by Rudolf Halin (1965), and is a precursor to the work of Robertson and Seymour linking treewidth to large grid minors, which became an important component of the algorithmic theory of bidimensionality.

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. Halin (1964) defined two rays r₀ and r₁ to be equivalent if there exists a ray r₂ that includes infinitely many vertices from each of them. This is an equivalence relation, and its equivalence classes (sets of mutually equivalent rays) are called the ends of the graph. Halin (1965) 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 cubic planar 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 r₂ in the definition of equivalence of rays (no matter what rays r₀ and r₁ are given), 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.

...
Wikipedia