Charles Pierre Trémaux

In graph theory, a Trémaux tree of an undirected graph G is a spanning tree of G, rooted at one of its vertices, with the property that every two adjacent vertices in G are related to each other as an ancestor and descendant in the tree. All depth-first search trees and all Hamiltonian paths are Trémaux trees. Trémaux trees are named after Charles Pierre Trémaux, a 19th-century French author who used a form of depth-first search as a strategy for solving mazes. They have also been called normal spanning trees, especially in the context of infinite graphs.

In finite graphs, although depth-first search itself is inherently sequential, Trémaux trees can be constructed by a randomized parallel algorithm in the complexity class RNC. They can be used to define the tree-depth of a graph, and as part of the left-right planarity test for testing whether a graph is a planar graph. A characterization of Trémaux trees in the monadic second-order logic of graphs allows graph properties involving orientations to be recognized efficiently for graphs of bounded treewidth using Courcelle's theorem.

Not every infinite graph has a Trémaux tree, and the graphs that do have them can be characterized by their forbidden minors. A Trémaux tree exists in every graph with countably many vertices, even when an infinite form of depth-first search would not succeed in exploring every vertex of the graph. In an infinite graph, a Trémaux tree must have exactly one infinite path for each end of the graph, and the existence of a Trémaux tree characterizes the graphs whose topological completions, formed by adding a point at infinity for each end, are metric spaces.

...
Wikipedia