A short proof of Halin’s grid theorem.pdf

¨ HAMBURGER BEITRAGE ZUR MATHEMATIK Heft 193 A short proof on Halin’s grid theorem Reinhard Diestel, Hamburg ¨ Marz 2004 A short proof of Halin’s grid theorem Rudolf Halin zum 70. Geburtstag Reinhard Diestel We give a short proof of Halin’s theorem that every thick end of a graph contains the infinite grid. Introduction An end of an infinite graph G is called thick if there are infinitely many disjoint rays (1-way infinite paths) in G all converging to that end. The infinite grid is an obvious example: it contains infinitely many disjoint rays, which all converge to its unique end. It is one of Halin’s most striking theorems that this observation has a converse: whenever G has a thick end ω , it contains a subdivision of an infinite hexagonal grid whose rays all converge to ω . The aim of this note is to give a short proof of Halin’s theorem. We follow Halin [ 3 ] in defining an end of a graph as an equivalence class of rays, where two rays are equivalent if no finite set of vertices separates them.1 In these terms, an end is thick if it contains infinitely many disjoint rays. The subrays of a ray are its tails, and an A–B path has no inner vertices in A ∪ B . See [ 1 ] for details of this or any other undefined terms used below. Let G be the N ×N grid, ie., the graph on N ×N in which two vertices are adjacent if and only if their Euclidean distance is 1. To define our standard copy H of the hexagonal grid, we delete from G the vertex (0, 0), the vertices (n, m) with n m, and all edges (n, m)(n + 1, m) such that n and m have equal parity (Fig