Trémaux tree

<h2 id="definition-and-examples">Definition and examples</h2>
<p>A Trémaux tree, for a graph 
  
    
      
        G
      
    
    {\displaystyle G}
  
, is a <a href="/facts/Spanning_tree/qQPN9taR">spanning tree</a> 
  
    
      
        T
      
    
    {\displaystyle T}
  
 with the property that, for every edge 
  
    
      
        u
        v
      
    
    {\displaystyle uv}
  
 in 
  
    
      
        G
      
    
    {\displaystyle G}
  
, one of the two endpoints 
  
    
      
        u
      
    
    {\displaystyle u}
  
 and 
  
    
      
        v
      
    
    {\displaystyle v}
  
 is an ancestor of the other. To be a spanning tree, it must only use edges of 
  
    
      
        G
      
    
    {\displaystyle G}
  
, 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.
</p><p>If a finite graph has a <a href="/facts/Hamiltonian_path/MHjY2xoY">Hamiltonian path</a>, then rooting that path at one of its two endpoints produces a Trémaux tree. For such a path, every pair of vertices is an ancestor–descendant pair.
</p><p>In the graph shown below, the tree with edges 1–3, 2–3, and 3–4 is a Trémaux tree when it is rooted at vertex 1 or vertex 2: every edge of the graph belongs to the tree except for the edge 1–2, which (for these choices of root) connects an ancestor-descendant pair.
</p>

<p>However, rooting the same tree at vertex 3 or vertex 4 produces a rooted tree that is not a Trémaux tree, because with this root 1 and 2 are no longer an ancestor and descendant of each other.
</p>
<h2 id="in-finite-graphs">In finite graphs</h2>
<h3>Existence</h3>
<p>Every finite <a href="/facts/Connected_graph/FSNjsYhz">connected</a> <a href="/facts/Undirected_graph/kw3eIBUe">undirected graph</a> has at least one Trémaux tree.<a class="footnote-ref" id="fnref:5" href="#fn:5"><sup>5</sup></a> One can construct such a tree by performing a <a href="/facts/Depth-first_search/luxJKVph">depth-first search</a> and connecting each vertex (other than the starting vertex of the search) to the earlier vertex from which it was discovered. The tree constructed in this way is known as a depth-first search tree. If 
  
    
      
        u
        v
      
    
    {\displaystyle uv}
  
 is an arbitrary edge in the graph, and 
  
    
      
        u
      
    
    {\displaystyle u}
  
 is the earlier of the two vertices to be reached by the search, then 
  
    
      
        v
      
    
    {\displaystyle v}
  
 must belong to the subtree descending from 
  
    
      
        u
      
    
    {\displaystyle u}
  
 in the depth-first search tree, because the search will necessarily discover 
  
    
      
        v
      
    
    {\displaystyle v}
  
 while it is exploring this subtree, either from one of the other vertices in the subtree or, failing that, from 
  
    
      
        u
      
    
    {\displaystyle u}
  
 directly. Every finite Trémaux tree can be generated as a depth-first search tree: If 
  
    
      
        T
      
    
    {\displaystyle T}
  
 is a Trémaux tree of a finite graph, and a depth-first search explores the children in 
  
    
      
        T
      
    
    {\displaystyle T}
  
 of each vertex prior to exploring any other vertices, it will necessarily generate 
  
    
      
        T
      
    
    {\displaystyle T}
  
 as its depth-first search tree.
</p>
<h3>Parallel construction</h3>

Unsolved problem in computer science:
Is there a deterministic parallel <i>NC</i> algorithm for constructing Trémaux trees?
<a href="/facts/List_of_unsolved_problems_in_computer_science/QySnBJ5E">(more unsolved problems in computer science)</a>

<p>It is <a href="/facts/P-complete/IX3sXDxl">P-complete</a> to find the Trémaux tree that would be found by a sequential depth-first search algorithm, in which the neighbors of each vertex are searched in order by their identities.<a class="footnote-ref" id="fnref:6" href="#fn:6"><sup>6</sup></a> Nevertheless, it is possible to find a different Trémaux tree by a randomized <a href="/facts/Parallel_algorithm/nUPzEF4C">parallel algorithm</a>, showing that the construction of Trémaux trees belongs to the complexity class <a href="/facts/NC_(complexity)/4SY2L2Kg">RNC</a>. The algorithm is based on another randomized parallel algorithm, for finding <a href="/facts/Matching_(graph_theory)/s0pUJ7hd">minimum-weight perfect matchings</a> in 0-1-weighted graphs.<a class="footnote-ref" id="fnref:7" href="#fn:7"><sup>7</sup></a> As of 1997, it remained unknown whether Trémaux tree construction could be performed by a deterministic parallel algorithm, in the complexity class <a href="/facts/NC_(complexity)/4SY2L2Kg">NC</a>.<a class="footnote-ref" id="fnref:8" href="#fn:8"><sup>8</sup></a> If matchings can be found in NC, then so can Trémaux trees.<a class="footnote-ref" id="fnref:9" href="#fn:9"><sup>9</sup></a>
</p>
<h3>Logical expression</h3>
<p>It is possible to express the property that a set 
  
    
      
        T
      
    
    {\displaystyle T}
  
 of edges with a choice of root vertex 
  
    
      
        r
      
    
    {\displaystyle r}
  
 forms a Trémaux tree, in the monadic second-order <a href="/facts/Logic_of_graphs/Pr5Cb5n1">logic of graphs</a>, 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:
</p>
<ul><li>The graph is connected by the edges in 
  
    
      
        T
      
    
    {\displaystyle T}
  
. This can be expressed logically as the statement that, for every non-empty proper subset of the graph's vertices, there exists an edge in 
  
    
      
        T
      
    
    {\displaystyle T}
  
 with exactly one endpoint in the given subset.</li>
<li>
  
    
      
        T
      
    
    {\displaystyle T}
  
 is acyclic. This can be expressed logically as the statement that there does not exist a nonempty subset 
  
    
      
        C
      
    
    {\displaystyle C}
  
 of 
  
    
      
        T
      
    
    {\displaystyle T}
  
 for which each vertex is incident to either zero or two edges of 
  
    
      
        C
      
    
    {\displaystyle C}
  
.</li>
<li>Every edge 
  
    
      
        e
      
    
    {\displaystyle e}
  
 not in 
  
    
      
        T
      
    
    {\displaystyle T}
  
 connects an ancestor-descendant pair of vertices in 
  
    
      
        T
      
    
    {\displaystyle T}
  
. This is true when both endpoints of 
  
    
      
        e
      
    
    {\displaystyle e}
  
 belong to a path in 
  
    
      
        T
      
    
    {\displaystyle T}
  
. It can be expressed logically as the statement that, for all edges 
  
    
      
        e
      
    
    {\displaystyle e}
  
, there exists a subset 
  
    
      
        P
      
    
    {\displaystyle P}
  
 of 
  
    
      
        T
      
    
    {\displaystyle T}
  
 such that exactly two vertices, one of them 
  
    
      
        r
      
    
    {\displaystyle r}
  
, are incident to a single edge of 
  
    
      
        P
      
    
    {\displaystyle P}
  
, and such that both endpoints of 
  
    
      
        e
      
    
    {\displaystyle e}
  
 are incident to at least one edge of 
  
    
      
        P
      
    
    {\displaystyle P}
  
.</li></ul>
<p>Once a Trémaux tree has been identified in this way, one can describe an <a href="/facts/Orientation_(graph_theory)/GV2KdNtn">orientation</a> 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. The remaining edges outside this set must be oriented in the other direction. 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 <a href="/facts/Treewidth/uoITxzRJ">treewidth</a> using <a href="/facts/Courcelle%27s_theorem/Yy83uBvh">Courcelle's theorem</a>.<a class="footnote-ref" id="fnref:10" href="#fn:10"><sup>10</sup></a>
</p>
<h3>Related properties</h3>
<p>If a graph has a <a href="/facts/Hamiltonian_path/MHjY2xoY">Hamiltonian path</a>, then that path (rooted at one of its endpoints) is also a Trémaux tree. The undirected graphs for which every Trémaux tree has this form are the <a href="/facts/Cycle_graph/bYhnPDHc">cycle graphs</a>, <a href="/facts/Complete_graph/AYD6hUqI">complete graphs</a>, and balanced <a href="/facts/Complete_bipartite_graph/C1RYIdpX">complete bipartite graphs</a>.<a class="footnote-ref" id="fnref:11" href="#fn:11"><sup>11</sup></a>
</p><p>Trémaux trees are closely related to the concept of <a href="/facts/Tree-depth/HtNMxVIz">tree-depth</a>. The tree-depth of a graph 
  
    
      
        G
      
    
    {\displaystyle G}
  
 can be defined as the smallest number 
  
    
      
        d
      
    
    {\displaystyle d}
  
 for which there exist a graph 
  
    
      
        H
      
    
    {\displaystyle H}
  
, with a Trémaux tree 
  
    
      
        T
      
    
    {\displaystyle T}
  
 of height 
  
    
      
        d
      
    
    {\displaystyle d}
  
, such that 
  
    
      
        G
      
    
    {\displaystyle G}
  
 is a subgraph of 
  
    
      
        H
      
    
    {\displaystyle H}
  
. Bounded tree-depth, in a family of graphs, is equivalent to the existence of a path that cannot occur as a <a href="/facts/Graph_minor/qn5eI22T">graph minor</a> of the graphs in the family. Many hard computational problems on graphs have algorithms that are <a href="/facts/Parameterized_complexity/RoyaJGgJ">fixed-parameter tractable</a> when parameterized by the tree-depth of their inputs.<a class="footnote-ref" id="fnref:12" href="#fn:12"><sup>12</sup></a>
</p><p>Trémaux trees also play a key role in the <a href="/facts/Fraysseix%E2%80%93Rosenstiehl_planarity_criterion/AayPX084">Fraysseix–Rosenstiehl planarity criterion</a> for testing whether a given graph is <a href="/facts/Planar_graph/plREagr9">planar</a>. According to this criterion, a graph 
  
    
      
        G
      
    
    {\displaystyle G}
  
 is planar if, for a given Trémaux tree 
  
    
      
        T
      
    
    {\displaystyle T}
  
 of 
  
    
      
        G
      
    
    {\displaystyle G}
  
, the remaining edges can be placed in a consistent way to the left or the right of the tree, subject to constraints that prevent edges with the same placement from crossing each other.<a class="footnote-ref" id="fnref:13" href="#fn:13"><sup>13</sup></a>
</p>
<h2 id="in-infinite-graphs">In infinite graphs</h2>
<h3>Existence</h3>
<p>Not every infinite graph has a normal spanning tree. For instance, a <a href="/facts/Complete_graph/AYD6hUqI">complete graph</a> on an <a href="/facts/Uncountable_set/zl2WqyJQ">uncountable set</a> 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 <a href="/facts/Countable_set/Wj4DmWPv">countable set</a> of vertices does have a normal spanning tree.<a class="footnote-ref" id="fnref:14" href="#fn:14"><sup>14</sup></a><a class="footnote-ref" id="fnref:15" href="#fn:15"><sup>15</sup></a>
</p><p>Even in countable graphs, a depth-first search might not succeed in eventually exploring the entire graph,<a class="footnote-ref" id="fnref:16" href="#fn:16"><sup>16</sup></a> 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).
</p>
<h3>Minors</h3>
<p>If an infinite graph 
  
    
      
        G
      
    
    {\displaystyle G}
  
 has a normal spanning tree, so does every connected <a href="/facts/Graph_minor/qn5eI22T">graph minor</a> of 
  
    
      
        G
      
    
    {\displaystyle G}
  
. It follows from this that the graphs that have normal spanning trees have a characterization by <a href="/facts/Forbidden_graph_characterization/50Kex6JU">forbidden</a> <a href="/facts/Graph_minor/qn5eI22T">minors</a>. One of the two classes of forbidden minors consists of <a href="/facts/Bipartite_graph/xWcXV9MB">bipartite graphs</a> 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 <a href="/facts/Aronszajn_tree/GASB35JW">Aronszajn trees</a>.<a class="footnote-ref" id="fnref:17" href="#fn:17"><sup>17</sup></a>
</p><p>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 <a href="/facts/Martin%27s_axiom/TvtNNj1o">Martin's axiom</a> is true and the <a href="/facts/Continuum_hypothesis/R0yGqHND">continuum hypothesis</a> 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.<a class="footnote-ref" id="fnref:18" href="#fn:18"><sup>18</sup></a>
</p>
<h3>Ends and metrizability</h3>
<p>Normal spanning trees are also closely related to the <a href="/facts/End_(graph_theory)/l5B9xEQz">ends</a> of an infinite graph, equivalence classes of infinite paths that, intuitively, go to infinity in the same direction. If a graph has a normal spanning tree, this tree must have exactly one infinite path for each of the graph's ends.<a class="footnote-ref" id="fnref:19" href="#fn:19"><sup>19</sup></a>
</p><p>An infinite graph can be used to form a <a href="/facts/Topological_space/v2ut7CbK">topological space</a> by viewing the graph itself as a <a href="/facts/Simplicial_complex/fF2282CF">simplicial complex</a> and adding a <a href="/facts/Point_at_infinity/GAuS0wHQ">point at infinity</a> for each end of the graph. With this topology, a graph has a normal spanning tree if and only if its set of vertices can be decomposed into a countable union of <a href="/facts/Closed_set/upYnRTUj">closed sets</a>. Additionally, this topological space can be represented by a <a href="/facts/Metric_space/gnBBRXtc">metric space</a> if and only if the graph has a normal spanning tree.<a class="footnote-ref" id="fnref:20" href="#fn:20"><sup>20</sup></a>
</p>

<h2 id="references">References</h2>

<ol>
<li id="fn:1"><p>Even, Shimon (2011), Graph Algorithms (2nd ed.), Cambridge University Press, pp. 46–48, ISBN 978-0-521-73653-4. <a href="978-0-521-73653-4" target="_blank">978-0-521-73653-4</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li>
<li id="fn:2"><p>Sedgewick, Robert (2002), Algorithms in C++: Graph Algorithms (3rd ed.), Pearson Education, pp. 149–157, ISBN 978-0-201-36118-6. <a href="978-0-201-36118-6" target="_blank">978-0-201-36118-6</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li>
<li id="fn:3"><p>Soukup, Lajos (2008), "Infinite combinatorics: from finite to infinite", Horizons of Combinatorics, Bolyai Soc. Math. Stud., vol. 17, Berlin: Springer, pp. 189–213, doi:10.1007/978-3-540-77200-2_10, ISBN 978-3-540-77199-9, MR 2432534. See in particular Theorem 3, p. 193. <a href="978-3-540-77199-9" target="_blank">978-3-540-77199-9</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></p></li>
<li id="fn:4"><p>Diestel, Reinhard (2017), Graph Theory, Graduate Texts in Mathematics, vol. 173 (5th ed.), Berlin: Springer, pp. 34–36, 220–221, 247, 251–252, doi:10.1007/978-3-662-53622-3, ISBN 978-3-662-53621-6, MR 3644391 <a href="978-3-662-53621-6" target="_blank">978-3-662-53621-6</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></p></li>
<li id="fn:5"><p>Diestel, Reinhard (2017), Graph Theory, Graduate Texts in Mathematics, vol. 173 (5th ed.), Berlin: Springer, pp. 34–36, 220–221, 247, 251–252, doi:10.1007/978-3-662-53622-3, ISBN 978-3-662-53621-6, MR 3644391 <a href="978-3-662-53621-6" target="_blank">978-3-662-53621-6</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></p></li>
<li id="fn:6"><p>Reif, John H. (1985), "Depth-first search is inherently sequential", Information Processing Letters, 20 (5): 229–234, doi:10.1016/0020-0190(85)90024-9, MR 0801987. <a href="/wiki/John_Reif" target="_blank">/wiki/John_Reif</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></p></li>
<li id="fn:7"><p>Aggarwal, A.; Anderson, R. J. (1988), "A random NC algorithm for depth first search", Combinatorica, 8 (1): 1–12, doi:10.1007/BF02122548, MR 0951989, S2CID 29440871. <a href="/wiki/Combinatorica" target="_blank">/wiki/Combinatorica</a> <a href="#fnref:7" class="footnote-back-ref">↩</a></p></li>
<li id="fn:8"><p>Karger, David R.; Motwani, Rajeev (1997), "An NC algorithm for minimum cuts", SIAM Journal on Computing, 26 (1): 255–272, doi:10.1137/S0097539794273083, MR 1431256. <a href="/wiki/David_Karger" target="_blank">/wiki/David_Karger</a> <a href="#fnref:8" class="footnote-back-ref">↩</a></p></li>
<li id="fn:9"><p>Aggarwal, A.; Anderson, R. J. (1988), "A random NC algorithm for depth first search", Combinatorica, 8 (1): 1–12, doi:10.1007/BF02122548, MR 0951989, S2CID 29440871. <a href="/wiki/Combinatorica" target="_blank">/wiki/Combinatorica</a> <a href="#fnref:9" class="footnote-back-ref">↩</a></p></li>
<li id="fn:10"><p>Courcelle, Bruno (1996), "On the expression of graph properties in some fragments of monadic second-order logic" (PDF), in Immerman, Neil; Kolaitis, Phokion G. (eds.), Proc. Descr. Complex. Finite Models, DIMACS, vol. 31, Amer. Math. Soc., pp. 33–62, MR 1451381. <a href="/wiki/Bruno_Courcelle" target="_blank">/wiki/Bruno_Courcelle</a> <a href="#fnref:10" class="footnote-back-ref">↩</a></p></li>
<li id="fn:11"><p>Chartrand, Gary; Kronk, Hudson V. (1968), "Randomly traceable graphs", SIAM Journal on Applied Mathematics, 16 (4): 696–700, doi:10.1137/0116056, MR 0234852. <a href="/wiki/Gary_Chartrand" target="_blank">/wiki/Gary_Chartrand</a> <a href="#fnref:11" class="footnote-back-ref">↩</a></p></li>
<li id="fn:12"><p>Nešetřil, Jaroslav; Ossona de Mendez, Patrice (2012), "Chapter 6. Bounded height trees and tree-depth", Sparsity: Graphs, Structures, and Algorithms, Algorithms and Combinatorics, vol. 28, Heidelberg: Springer, pp. 115–144, doi:10.1007/978-3-642-27875-4, ISBN 978-3-642-27874-7, MR 2920058. <a href="978-3-642-27874-7" target="_blank">978-3-642-27874-7</a> <a href="#fnref:12" class="footnote-back-ref">↩</a></p></li>
<li id="fn:13"><p>de Fraysseix, Hubert; Rosenstiehl, Pierre (1982), "A depth-first-search characterization of planarity", Graph theory (Cambridge, 1981), Ann. Discrete Math., vol. 13, Amsterdam: North-Holland, pp. 75–80, MR 0671906; de Fraysseix, Hubert; Ossona de Mendez, Patrice; Rosenstiehl, Pierre (2006), "Trémaux trees and planarity", International Journal of Foundations of Computer Science, 17 (5): 1017–1029, arXiv:math/0610935, doi:10.1142/S0129054106004248, MR 2270949. <a href="/wiki/Pierre_Rosenstiehl" target="_blank">/wiki/Pierre_Rosenstiehl</a> <a href="#fnref:13" class="footnote-back-ref">↩</a></p></li>
<li id="fn:14"><p>Soukup, Lajos (2008), "Infinite combinatorics: from finite to infinite", Horizons of Combinatorics, Bolyai Soc. Math. Stud., vol. 17, Berlin: Springer, pp. 189–213, doi:10.1007/978-3-540-77200-2_10, ISBN 978-3-540-77199-9, MR 2432534. See in particular Theorem 3, p. 193. <a href="978-3-540-77199-9" target="_blank">978-3-540-77199-9</a> <a href="#fnref:14" class="footnote-back-ref">↩</a></p></li>
<li id="fn:15"><p>Diestel, Reinhard (2017), Graph Theory, Graduate Texts in Mathematics, vol. 173 (5th ed.), Berlin: Springer, pp. 34–36, 220–221, 247, 251–252, doi:10.1007/978-3-662-53622-3, ISBN 978-3-662-53621-6, MR 3644391 <a href="978-3-662-53621-6" target="_blank">978-3-662-53621-6</a> <a href="#fnref:15" class="footnote-back-ref">↩</a></p></li>
<li id="fn:16"><p>Soukup, Lajos (2008), "Infinite combinatorics: from finite to infinite", Horizons of Combinatorics, Bolyai Soc. Math. Stud., vol. 17, Berlin: Springer, pp. 189–213, doi:10.1007/978-3-540-77200-2_10, ISBN 978-3-540-77199-9, MR 2432534. See in particular Theorem 3, p. 193. <a href="978-3-540-77199-9" target="_blank">978-3-540-77199-9</a> <a href="#fnref:16" class="footnote-back-ref">↩</a></p></li>
<li id="fn:17"><p>Diestel, Reinhard; Leader, Imre (2001), "Normal spanning trees, Aronszajn trees and excluded minors" (PDF), Journal of the London Mathematical Society, Second Series, 63 (1): 16–32, doi:10.1112/S0024610700001708, MR 1801714, S2CID 13980974. <a href="/wiki/Imre_Leader" target="_blank">/wiki/Imre_Leader</a> <a href="#fnref:17" class="footnote-back-ref">↩</a></p></li>
<li id="fn:18"><p>Bowler, Nathan; Geschke, Stefan; Pitz, Max (2016), Minimal obstructions for normal spanning trees, arXiv:1609.01042, Bibcode:2016arXiv160901042B <a href="/wiki/ArXiv_(identifier)" target="_blank">/wiki/ArXiv_(identifier)</a> <a href="#fnref:18" class="footnote-back-ref">↩</a></p></li>
<li id="fn:19"><p>Diestel, Reinhard (2006), "End spaces and spanning trees", Journal of Combinatorial Theory, Series B, 96 (6): 846–854, CiteSeerX 10.1.1.63.9751, doi:10.1016/j.jctb.2006.02.010, MR 2274079. <a href="/wiki/Journal_of_Combinatorial_Theory" target="_blank">/wiki/Journal_of_Combinatorial_Theory</a> <a href="#fnref:19" class="footnote-back-ref">↩</a></p></li>
<li id="fn:20"><p>Diestel, Reinhard (2006), "End spaces and spanning trees", Journal of Combinatorial Theory, Series B, 96 (6): 846–854, CiteSeerX 10.1.1.63.9751, doi:10.1016/j.jctb.2006.02.010, MR 2274079. <a href="/wiki/Journal_of_Combinatorial_Theory" target="_blank">/wiki/Journal_of_Combinatorial_Theory</a> <a href="#fnref:20" class="footnote-back-ref">↩</a></p></li>
</ol>

Trémaux tree open-in-new

Trémaux tree