I recently revisited the Wikipedia article on normal spanning trees, rooted spanning trees of infinite undirected graphs that act like depth-first search trees in the sense that every non-tree edge of the graph connects an ancestor to a descendant. They exist in every connected countable undirected graph, but cannot always be generated by a depth-first search. It occurred to me to wonder: in which connected countable undirected graphs is it possible for a depth-first search to visit all vertices? It turns out to be possible if and only if the graph has one of the following two connectivity properties. Either:

  • there exists a finite path \(P\) whose removal splits the remaining subgraph into infinitely many finite connected components, all but finitely many of which are adjacent to the endpoint of the path, or

  • deleting any finite path splits the remaining subgraph into a single infinite component and finitely many finite connected components.

If path \(P\) exists, we can guide a depth first search as follows: start at the other end of the path. Then, whenever the remaining unexplored vertices have a component adjacent to the current search vertex, start a recursive finite depth first search in one of these components, the one containing the earliest unexplored vertex in an enumeration of the graph’s vertices. Otherwise, take one more step along \(P\). This choice of which component to explore next ensures that every component will eventually be visited by the search.

In the second case, choose an arbitrary root for the depth first search, and then, at each step, while there is a finite component adjacent to the endpoint of the current search, chose one arbitrarily and explore it using a recursive finite depth first search. If there are no adjacent finite components, step into the infinite component along an edge that reduces the distance to the earliest unexplored vertex. Every finite component left by removing the depth-first search path will eventually be visited, from the last vertex adjacent to it on the search path, and the strategy of moving towards the earliest unexplored vertex ensures that the vertices that remain in the infinite component will also eventually be visited.

It remains to show that every graph that can be completely searched has one of these two properties. Consider any depth-first search that explores the whole graph. If there is a vertex \(v\) that is returned to infinitely often, then the depth-first search path to that vertex is a path \(P\) whose removal splits the remaining subgraph into infinitely many finite connected components: the components formed by the vertices between each repeat visit to \(v\), and possibly some finitely many earlier components. So when \(v\) exists, the graph mast have the first of the two connectivity properties.

On the other hand, suppose that no vertex is repeated infinitely often. Find an infinite ray \(R\) in the depth-first search tree that, from each vertex \(v\) in the path (starting from the root) chooses the next vertex in the ray to be the last vertex explored from \(v\). If any finite path \(P\) is removed from the graph, \(P\) and its depth-first ancestors can only cover finitely many vertices of \(R\). If \(P\) is removed, the rest of \(R\) and the finite branches of the depth-first search tree explored between repetitions along the rest of \(R\) all belong to a single infinite component. There are only finitely many other vertices which can form only finitely many finite components. So the graph must have the second of the two connectivity properties.

This may well all be known; I didn’t search very hard for prior work and my searches mostly turned up material on the more general normal spanning trees. If it is known, I would appreciate pointers to where it might be published.

(Discuss on Mastodon)