An exhaustion of a countable graph is an increasing sequence of finite vertex sets whose union is the whole vertex set. Enumerating the vertices and taking finite initial segments gives one. The induced finite subgraphs need not be connected graph.
For a connected graph that is a locally finite graph, the graph balls about a fixed vertex give a connected exhaustion: each ball is finite, and every vertex has finite graph distance from the centre. In a locally finite graph, any prescribed finite graph path, together with all graph neighbours of its visited vertices, lies in a sufficiently large exhaustion set. This permits coupling finite-volume and infinite-volume simple random walks up to a finite stopping time. A disconnected graph cannot have an exhaustion by connected vertex sets covering different connected components of a graph.

Articles by others on the same topic (0)

There are currently no matching articles.