A tree in which every vertex has finitely many incident edges; for a rooted tree this is equivalent to finitely many children per node. Induction on depth then shows every level from a single root is finite, even if the entire tree is infinite. Consequently ordinary breadth-first tree search can eventually reach each node, provided the elementary traversal operations terminate.
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
There are currently no matching articles.