Trémaux tree

[1][2] They have also been called normal spanning trees, especially in the context of infinite graphs.

The graphs that have Trémaux trees can be characterized by forbidden minors.

An infinite 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.

, and include every vertex, with a unique finite path between every pair of vertices.

Additionally, to define the ancestor–descendant relation in this tree, one of its vertices must be designated as its root.

Every finite connected undirected graph has at least one Trémaux tree.

is a Trémaux tree of a finite graph, and a depth-first search explores the children in

of each vertex prior to exploring any other vertices, it will necessarily generate

[5] Nevertheless, it is possible to find a different Trémaux tree by a randomized parallel algorithm, showing that the construction of Trémaux trees belongs to the complexity class RNC.

[6] As of 1997, it remained unknown whether Trémaux tree construction could be performed by a deterministic parallel algorithm, in the complexity class NC.

forms a Trémaux tree, in the monadic second-order logic of graphs, and more specifically in the form of this logic called MSO2, which allows quantification over both vertex and edge sets.

This property can be expressed as the conjunction of the following properties: Once a Trémaux tree has been identified in this way, one can describe an orientation of the given graph, also in monadic second-order logic, by specifying the set of edges whose orientation is from the ancestral endpoint to the descendant endpoint.

This technique allows graph properties involving orientations to be specified in monadic second order logic, allowing these properties to be tested efficiently on graphs of bounded treewidth using Courcelle's theorem.

[9] Trémaux trees are closely related to the concept of tree-depth.

Many hard computational problems on graphs have algorithms that are fixed-parameter tractable when parameterized by the tree-depth of their inputs.

For instance, a complete graph on an uncountable set of vertices does not have one: a normal spanning tree in a complete graph can only be a path, but a path has only a countable number of vertices.

However, every connected graph on a countable set of vertices does have a normal spanning tree.

[3][4] Even in countable graphs, a depth-first search might not succeed in eventually exploring the entire graph,[3] and not every normal spanning tree can be generated by a depth-first search: to be a depth-first search tree, a countable normal spanning tree must have only one infinite path or one node with infinitely many children (and not both).

has a normal spanning tree, so does every connected graph minor of

It follows from this that the graphs that have normal spanning trees have a characterization by forbidden minors.

One of the two classes of forbidden minors consists of bipartite graphs in which one side of the bipartition is countable, the other side is uncountable, and every vertex has infinite degree.

The other class of forbidden minors consists of certain graphs derived from Aronszajn trees.

[12] The details of this characterization depend on the choice of set-theoretic axiomatization used to formalize mathematics.

In particular, in models of set theory for which Martin's axiom is true and the continuum hypothesis is false, the class of bipartite graphs in this characterization can be replaced by a single forbidden minor.

However, for models in which the continuum hypothesis is true, this class contains graphs which are incomparable with each other in the minor ordering.

[13] Normal spanning trees are also closely related to the ends of an infinite graph, equivalence classes of infinite paths that, intuitively, go to infinity in the same direction.