A graph is locally finite when every vertex has finite degree.
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.

Ancestors (6)

  1. Degree (graph theory)
  2. Graph theory
  3. Foundations of mathematics
  4. Area of mathematics
  5. Mathematics
  6. Home

Discussion (0) New discussion

There are no discussions about this article yet.

Articles by others on the same topic (0)

There are currently no matching articles.