Trémaux tree

Summary

In graph theory, a Trémaux tree of an undirected graph $G$ is a type of spanning tree, generalizing depth-first search trees. They are defined by the property that every edge of $G$ connects an ancestor–descendant pair in the tree. 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.