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 connected graph vertex sets whose union is the whole graph vertex set. In a locally finite graph, every prescribed finite graph path together with all graph neighbours of its visited graph 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.
Articles by others on the same topic
There are currently no matching articles.