Tree (graph theory)

<h2 id="definitions">Definitions</h2>
<h3>Tree</h3>
A tree is an undirected graph G that satisfies any of the following equivalent conditions:

<ul><li>G is <a href="/facts/Connected_graph/FSNjsYhz">connected</a> and <a href="/facts/Cycle_(graph_theory)/Is44edrv">acyclic</a> (contains no cycles).</li>
<li>G is acyclic, and a simple cycle is formed if any <a href="/facts/Edge_(graph_theory)/W0MqKkyE">edge</a> is added to G.</li>
<li>G is connected, but would become <a href="/facts/Connectivity_(graph_theory)/FSNjsYhz">disconnected</a> if any single edge is removed from G.</li>
<li>G is connected and the <a href="/facts/Complete_graph/AYD6hUqI">complete graph</a> K3 is not a <a href="/facts/Minor_(graph_theory)/qn5eI22T">minor</a> of G.</li>
<li>Any two vertices in G can be connected by a unique <a href="/facts/Path_(graph_theory)/WMsq21Nf">simple path</a>.</li></ul>
If G has finitely many vertices, say n of them, then the above statements are also equivalent to any of the following conditions:

<ul><li>G is connected and has n − 1 edges.</li>
<li>G is connected, and every <a href="/facts/Subgraph_(graph_theory)/W0MqKkyE">subgraph</a> of G includes at least one vertex with zero or one incident edges. (That is, G is connected and <a href="/facts/Degeneracy_(graph_theory)/IaYkus22">1-degenerate</a>.)</li>
<li>G has no simple cycles and has n − 1 edges.</li></ul>
As elsewhere in graph theory, the <a href="/facts/Order-zero_graph/Ro1YV0g6">order-zero graph</a> (graph with no vertices) is generally not considered to be a tree: while it is vacuously connected as a graph (any two vertices can be connected by a path), it is not <a href="/facts/N-connected/dbCgWgu3">0-connected</a> (or even (−1)-connected) in algebraic topology, unlike non-empty trees, and violates the "one more vertex than edges" relation. It may, however, be considered as a forest consisting of zero trees.
An internal vertex (or inner vertex) is a vertex of <a href="/facts/Degree_(graph_theory)/LnFFpI8v">degree</a> at least 2. Similarly, an external vertex (or outer vertex, terminal vertex or leaf) is a vertex of degree 1. A branch vertex in a tree is a vertex of degree at least 3.<a class="footnote-ref" id="fnref:21" href="#fn:21">21</a>
An irreducible tree (or series-reduced tree) is a tree in which there is no vertex of degree 2 (enumerated at sequence A000014 in the <a href="/facts/OEIS/yow6cVsU">OEIS</a>).<a class="footnote-ref" id="fnref:22" href="#fn:22">22</a>

<h3>Forest</h3>
A forest is an undirected acyclic graph or equivalently a <a href="/facts/Disjoint_union_of_graphs/J0eE3mpB">disjoint union</a> of trees. Trivially so, each connected component of a forest is a tree. As special cases, the order-zero graph (a forest consisting of zero trees), a single tree, and an edgeless graph, are examples of forests.
Since for every tree V − E = 1, we can easily count the number of trees that are within a forest by subtracting the difference between total vertices and total edges. V − E = number of trees in a forest.

<h3>Polytree</h3>
Main article: <a href="/facts/Polytree/pcJa4qeS">Polytree</a>
A polytree<a class="footnote-ref" id="fnref:23" href="#fn:23">23</a> (or directed tree<a class="footnote-ref" id="fnref:24" href="#fn:24">24</a> or oriented tree<a class="footnote-ref" id="fnref:25" href="#fn:25">25</a><a class="footnote-ref" id="fnref:26" href="#fn:26">26</a> or singly connected network<a class="footnote-ref" id="fnref:27" href="#fn:27">27</a>) is a <a href="/facts/Directed_acyclic_graph/k6zq1os9">directed acyclic graph</a> (DAG) whose underlying undirected graph is a tree. In other words, if we replace its directed edges with undirected edges, we obtain an undirected graph that is both connected and acyclic.
Some authors restrict the phrase "directed tree" to the case where the edges are all directed towards a particular vertex, or all directed away from a particular vertex (see <a href="/facts/Arborescence_(graph_theory)/qFKvoaLJ">arborescence</a>).<a class="footnote-ref" id="fnref:28" href="#fn:28">28</a><a class="footnote-ref" id="fnref:29" href="#fn:29">29</a><a class="footnote-ref" id="fnref:30" href="#fn:30">30</a>

<h3>Polyforest</h3>
A polyforest (or directed forest or oriented forest) is a directed acyclic graph whose underlying undirected graph is a forest. In other words, if we replace its directed edges with undirected edges, we obtain an undirected graph that is acyclic.
As with directed trees, some authors restrict the phrase "directed forest" to the case where the edges of each connected component are all directed towards a particular vertex, or all directed away from a particular vertex (see <a href="/facts/Arborescence_(graph_theory)/qFKvoaLJ">branching</a>).<a class="footnote-ref" id="fnref:31" href="#fn:31">31</a>

<h3>Rooted tree</h3>
A rooted tree is a tree in which one vertex has been designated the root.<a class="footnote-ref" id="fnref:32" href="#fn:32">32</a> The edges of a rooted tree can be assigned a natural orientation, either away from or towards the root, in which case the structure becomes a directed rooted tree. When a directed rooted tree has an orientation away from the root, it is called an arborescence<a class="footnote-ref" id="fnref:33" href="#fn:33">33</a> or out-tree;<a class="footnote-ref" id="fnref:34" href="#fn:34">34</a> when it has an orientation towards the root, it is called an anti-arborescence or in-tree.<a class="footnote-ref" id="fnref:35" href="#fn:35">35</a> The tree-order is the <a href="/facts/Partial_ordering/qb4a3FAX">partial ordering</a> on the vertices of a tree with u < v if and only if the unique path from the root to v passes through u. A rooted tree T that is a <a href="/facts/Glossary_of_graph_theory/W0MqKkyE">subgraph</a> of some graph G is a <a href="/facts/Normal_tree/T0uFMTHt">normal tree</a> if the ends of every T-path in G are comparable in this tree-order (Diestel 2005, p. 15). Rooted trees, often with an additional structure such as an ordering of the neighbors at each vertex, are a key data structure in computer science; see <a href="/facts/Tree_data_structure/RcXz9noF">tree data structure</a>.
In a context where trees typically have a root, a tree without any designated root is called a free tree.
A labeled tree is a tree in which each vertex is given a unique label. The vertices of a labeled tree on n vertices (for nonnegative integers n) are typically given the labels 1, 2, …, n. A <a href="/facts/Recursive_tree/GW33L27P">recursive tree</a> is a labeled rooted tree where the vertex labels respect the tree order (i.e., if u < v for two vertices u and v, then the label of u is smaller than the label of v).
In a rooted tree, the parent of a vertex v is the vertex connected to v on the <a href="/facts/Path_(graph_theory)/WMsq21Nf">path</a> to the root; every vertex has a unique parent, except the root has no parent.<a class="footnote-ref" id="fnref:36" href="#fn:36">36</a> A child of a vertex v is a vertex of which v is the parent.<a class="footnote-ref" id="fnref:37" href="#fn:37">37</a> An ascendant of a vertex v is any vertex that is either the parent of v or is (recursively) an ascendant of a parent of v. A descendant of a vertex v is any vertex that is either a child of v or is (recursively) a descendant of a child of v. A sibling to a vertex v is any other vertex on the tree that shares a parent with v.<a class="footnote-ref" id="fnref:38" href="#fn:38">38</a> A leaf is a vertex with no children.<a class="footnote-ref" id="fnref:39" href="#fn:39">39</a> An internal vertex is a vertex that is not a leaf.<a class="footnote-ref" id="fnref:40" href="#fn:40">40</a>
The height of a vertex in a rooted tree is the length of the longest downward path to a leaf from that vertex. The height of the tree is the height of the root. The depth of a vertex is the length of the path to its root (root path). The depth of a tree is the maximum depth of any vertex. Depth is commonly needed in the manipulation of the various self-balancing trees, <a href="/facts/AVL_tree/DfexIbS6">AVL trees</a> in particular. The root has depth zero, leaves have height zero, and a tree with only a single vertex (hence both a root and leaf) has depth and height zero. Conventionally, an empty tree (a tree with no vertices, if such are allowed) has depth and height −1.
A <a href="/facts/K-ary_tree/XAMJC3QW">k-ary tree</a> (for nonnegative integers k) is a rooted tree in which each vertex has at most k children.<a class="footnote-ref" id="fnref:41" href="#fn:41">41</a> 2-ary trees are often called <a href="/facts/Binary_tree/TDV7GMpu">binary trees</a>, while 3-ary trees are sometimes called <a href="/facts/Ternary_tree/WvNM5JzM">ternary trees</a>.

<h3> Ordered tree</h3>
An ordered tree (alternatively, plane tree or positional tree<a class="footnote-ref" id="fnref:42" href="#fn:42">42</a>) is a rooted tree in which an ordering is specified for the children of each vertex.<a class="footnote-ref" id="fnref:43" href="#fn:43">43</a><a class="footnote-ref" id="fnref:44" href="#fn:44">44</a> This is called a "plane tree" because an ordering of the children is equivalent to an embedding of the tree in the plane, with the root at the top and the children of each vertex lower than that vertex. Given an embedding of a rooted tree in the plane, if one fixes a direction of children, say left to right, then an embedding gives an ordering of the children. Conversely, given an ordered tree, and conventionally drawing the root at the top, then the child vertices in an ordered tree can be drawn left-to-right, yielding an essentially unique planar embedding.

<h2 id="properties">Properties</h2>
<ul><li>Every tree is a <a href="/facts/Bipartite_graph/xWcXV9MB">bipartite graph</a>. A graph is bipartite if and only if it contains no cycles of odd length. Since a tree contains no cycles at all, it is bipartite.</li>
<li>Every tree with only <a href="/facts/Countable_set/Wj4DmWPv">countably</a> many vertices is a <a href="/facts/Planar_graph/plREagr9">planar graph</a>.</li>
<li>Every connected graph G admits a <a href="/facts/Spanning_tree_(mathematics)/qQPN9taR">spanning tree</a>, which is a tree that contains every vertex of G and whose edges are edges of G. More specific types spanning trees, existing in every connected finite graph, include <a href="/facts/Depth-first_search/luxJKVph">depth-first search</a> trees and <a href="/facts/Breadth-first_search/2kulDXCx">breadth-first search</a> trees. Generalizing the existence of depth-first-search trees, every connected graph with only <a href="/facts/Countable_set/Wj4DmWPv">countably</a> many vertices has a <a href="/facts/Tr%C3%A9maux_tree/T0uFMTHt">Trémaux tree</a>.<a class="footnote-ref" id="fnref:45" href="#fn:45">45</a> However, some <a href="/facts/Uncountable_set/zl2WqyJQ">uncountable</a>-<a href="/facts/Order_of_a_graph/kw3eIBUe">order</a> graphs do not have such a tree.<a class="footnote-ref" id="fnref:46" href="#fn:46">46</a></li>
<li>Every finite tree with n vertices, with n > 1, has at least two terminal vertices (leaves). This minimal number of leaves is characteristic of <a href="/facts/Path_graph/4Y2f35eM">path graphs</a>; the maximal number, n − 1, is attained only by <a href="/facts/Star_graph/PNW0H6eK">star graphs</a>. The number of leaves is at least the maximum vertex degree.</li>
<li>For any three vertices in a tree, the three paths between them have exactly one vertex in common. More generally, a vertex in a graph that belongs to three shortest paths among three vertices is called a median of these vertices. Because every three vertices in a tree have a unique median, every tree is a <a href="/facts/Median_graph/xl4m0C9I">median graph</a>.</li>
<li>Every tree has a <a href="/facts/Graph_center/C08yjerL">center</a> consisting of one vertex or two adjacent vertices. The center is the middle vertex or middle two vertices in every longest path. Similarly, every n-vertex tree has a centroid consisting of one vertex or two adjacent vertices. In the first case removal of the vertex splits the tree into subtrees of fewer than n/2 vertices. In the second case, removal of the edge between the two centroidal vertices splits the tree into two subtrees of exactly n/2 vertices.</li>
<li>The maximal cliques of a tree are precisely its edges, implying that the class of trees has <a href="/facts/Graphs_with_few_cliques/1kdUM5hY">few cliques</a>.</li></ul>
<h2 id="enumeration">Enumeration</h2>
<h3>Labeled trees</h3>
<a href="/facts/Cayley%27s_formula/fwjWPJTf">Cayley's formula</a> states that there are nn−2 trees on n labeled vertices. A classic proof uses <a href="/facts/Pr%C3%BCfer_sequence/0tmI33Mm">Prüfer sequences</a>, which naturally show a stronger result: the number of trees with vertices 1, 2, …, n of degrees d1, d2, …, dn respectively, is the <a href="/facts/Multinomial_theorem/0kyhtHvf">multinomial coefficient</a>

(
            
            
              
                n
                −
                2
              
              
                
                  d
                  
                    1
                  
                
                −
                1
                ,
                
                  d
                  
                    2
                  
                
                −
                1
                ,
                …
                ,
                
                  d
                  
                    n
                  
                
                −
                1
              
            
            
              )
            
          
        
        .
      
    
    {\displaystyle {n-2 \choose d_{1}-1,d_{2}-1,\ldots ,d_{n}-1}.}

A more general problem is to count <a href="/facts/Spanning_tree/qQPN9taR">spanning trees</a> in an <a href="/facts/Undirected_graph/kw3eIBUe">undirected graph</a>, which is addressed by the <a href="/facts/Matrix_tree_theorem/pptIpEVc">matrix tree theorem</a>. (Cayley's formula is the special case of spanning trees in a <a href="/facts/Complete_graph/AYD6hUqI">complete graph</a>.) The similar problem of counting all the subtrees regardless of size is <a href="/facts/Sharp-P-complete/M6QgPJY6">#P-complete</a> in the general case (Jerrum (1994)).

<h3>Unlabeled trees</h3>
Counting the number of unlabeled free trees is a harder problem. No closed formula for the number t(n) of trees with n vertices <a href="/facts/Up_to/ydz4ztzX">up to</a> <a href="/facts/Graph_isomorphism/SBjVIhwW">graph isomorphism</a> is known. The first few values of t(n) are

1, 1, 1, 1, 2, 3, 6, 11, 23, 47, 106, 235, 551, 1301, 3159, … (sequence A000055 in the <a href="/facts/On-Line_Encyclopedia_of_Integer_Sequences/yow6cVsU">OEIS</a>).
Otter (1948) proved the asymptotic estimate

t
        (
        n
        )
        ∼
        C
        
          α
          
            n
          
        
        
          n
          
            −
            5
            
              /
            
            2
          
        
        
        
          as 
        
        n
        →
        ∞
        ,
      
    
    {\displaystyle t(n)\sim C\alpha ^{n}n^{-5/2}\quad {\text{as }}n\to \infty ,}

with C ≈ 0.534949606... and α ≈ 2.95576528565... (sequence A051491 in the <a href="/facts/On-Line_Encyclopedia_of_Integer_Sequences/yow6cVsU">OEIS</a>). Here, the ~ symbol means that

lim
          
            n
            →
            ∞
          
        
        
          
            
              t
              (
              n
              )
            
            
              C
              
                α
                
                  n
                
              
              
                n
                
                  −
                  5
                  
                    /
                  
                  2
                
              
            
          
        
        =
        1.
      
    
    {\displaystyle \lim _{n\to \infty }{\frac {t(n)}{C\alpha ^{n}n^{-5/2}}}=1.}

This is a consequence of his asymptotic estimate for the number r(n) of unlabeled rooted trees with n vertices:

r
        (
        n
        )
        ∼
        D
        
          α
          
            n
          
        
        
          n
          
            −
            3
            
              /
            
            2
          
        
        
        
          as 
        
        n
        →
        ∞
        ,
      
    
    {\displaystyle r(n)\sim D\alpha ^{n}n^{-3/2}\quad {\text{as }}n\to \infty ,}

with D ≈ 0.43992401257... and the same α as above (cf. Knuth (1997), chap. 2.3.4.4 and Flajolet & Sedgewick (2009), chap. VII.5, p. 475).
The first few values of r(n) are<a class="footnote-ref" id="fnref:47" href="#fn:47">47</a>

1, 1, 2, 4, 9, 20, 48, 115, 286, 719, 1842, 4766, 12486, 32973, … (sequence A000081 in the <a href="/facts/On-Line_Encyclopedia_of_Integer_Sequences/yow6cVsU">OEIS</a>).
<h2 id="types-of-trees">Types of trees</h2>
<ul><li>A <a href="/facts/Path_graph/4Y2f35eM">path graph</a> (or linear graph) consists of n vertices arranged in a line, so that vertices i and i + 1 are connected by an edge for i = 1, …, n – 1.</li>
<li>A <a href="/facts/Starlike_tree/kKbpCdRA">starlike tree</a> consists of a central vertex called root and several path graphs attached to it. More formally, a tree is starlike if it has exactly one vertex of degree greater than 2.</li>
<li>A <a href="/facts/Star_(graph_theory)/PNW0H6eK">star tree</a> is a tree which consists of a single internal vertex (and n – 1 leaves). In other words, a star tree of order n is a tree of order n with as many leaves as possible.</li>
<li>A <a href="/facts/Caterpillar_tree/bPYdGwms">caterpillar tree</a> is a tree in which all vertices are within distance 1 of a central path subgraph.</li>
<li>A <a href="/facts/List_of_graphs/vnIy3cny">lobster tree</a> is a tree in which all vertices are within distance 2 of a central path subgraph.</li>
<li>A regular tree of degree d is the infinite tree with d edges at each vertex. These arise as the <a href="/facts/Cayley_graph/QxoxNnys">Cayley graphs</a> of <a href="/facts/Free_group/zPo2NIGb">free groups</a>, and in the theory of <a href="/facts/Building_(mathematics)/916RYbEN">Tits buildings</a>. In <a href="/facts/Statistical_mechanics/6zMsNYYG">statistical mechanics</a> they are known as <a href="/facts/Bethe_lattice/DlKrFUcu">Bethe lattices</a>.</li></ul>
<h2 id="see-also">See also</h2>
<ul><li><a href="/facts/Decision_tree/XDVeGlkJ">Decision tree</a></li>
<li><a href="/facts/Hypertree/UCNHKxHG">Hypertree</a></li>
<li><a href="/facts/Multitree/xK7npdzB">Multitree</a></li>
<li><a href="/facts/Pseudoforest/Fm5fK5BH">Pseudoforest</a></li>
<li><a href="/facts/Tree_structure/R2vT5UIu">Tree structure</a> (general)</li>
<li><a href="/facts/Tree_(data_structure)/RcXz9noF">Tree (data structure)</a></li>
<li><a href="/facts/Unrooted_binary_tree/GM5KxPBh">Unrooted binary tree</a></li></ul>
<h2 id="notes">Notes</h2>

<ul><li>Bender, Edward A.; Williamson, S. Gill (2010), <a href="https://books.google.com/books?id=vaXv_yhefG8C">Lists, Decisions and Graphs. With an Introduction to Probability</a></li>
<li>Dasgupta, Sanjoy (1999), "Learning polytrees", <a href="http://cseweb.ucsd.edu/~dasgupta/papers/poly.pdf">Proc. 15th Conference on Uncertainty in Artificial Intelligence (UAI 1999), Stockholm, Sweden, July–August 1999</a> (PDF), pp. 134–141.</li>
<li>Deo, Narsingh (1974), <a href="https://www.edutechlearners.com/download/Graphtheory.pdf">Graph Theory with Applications to Engineering and Computer Science</a> (PDF), Englewood, New Jersey: Prentice-Hall, <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 0-13-363473-6, <a href="https://web.archive.org/web/20190517165158/http://www.edutechlearners.com/download/Graphtheory.pdf">archived</a> (PDF) from the original on 2019-05-17</li>
<li><a href="/facts/Frank_Harary/3J2P7l4w">Harary, Frank</a>; Prins, Geert (1959), <a href="https://projecteuclid.org/euclid.acta/1485889061">"The number of homeomorphically irreducible trees, and other species"</a>, <a href="/facts/Acta_Mathematica/11kbuhDT">Acta Mathematica</a>, 101 (1–2): 141–162, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1007%2FBF02559543">10.1007/BF02559543</a>, <a href="/facts/ISSN_(identifier)/DPAflDvU">ISSN</a> <a href="https://search.worldcat.org/issn/0001-5962">0001-5962</a></li>
<li><a href="/facts/Frank_Harary/3J2P7l4w">Harary, Frank</a>; Sumner, David (1980), "The dichromatic number of an oriented tree", Journal of Combinatorics, Information & System Sciences, 5 (3): 184–187, <a href="/facts/MR_(identifier)/uP137L11">MR</a> <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=0603363">0603363</a>.</li>
<li>Kim, Jin H.; Pearl, Judea (1983), "A computational model for causal and diagnostic reasoning in inference engines", <a href="https://www.ijcai.org/Proceedings/83-1/Papers/041.pdf">Proc. 8th International Joint Conference on Artificial Intelligence (IJCAI 1983), Karlsruhe, Germany, August 1983</a> (PDF), pp. 190–193.</li>
<li>Li, Gang (1996), "Generation of Rooted Trees and Free Trees", <a href="http://webhome.cs.uvic.ca/~ruskey/Theses/GangLiMScThesis.pdf">M.S. Thesis, Dept. of Computer Science, University of Victoria, BC, Canada</a> (PDF), p. 9.</li>
<li><a href="/facts/Rodica_Simion/dWEXlVIh">Simion, Rodica</a> (1991), "Trees with 1-factors and oriented trees", Discrete Mathematics, 88 (1): 93–104, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1016%2F0012-365X%2891%2990061-6">10.1016/0012-365X(91)90061-6</a>, <a href="/facts/MR_(identifier)/uP137L11">MR</a> <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=1099270">1099270</a>.</li></ul>
<h2 id="further-reading">Further reading</h2>

Wikimedia Commons has media related to Tree (graph theory).

<ul><li><a href="/facts/Reinhard_Diestel/Fzv2bX8x">Diestel, Reinhard</a> (2005), <a href="http://diestel-graph-theory.com/index.html">Graph Theory</a> (3rd ed.), Berlin, New York: Springer-Verlag, <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 978-3-540-26183-4.</li>
<li>Flajolet, Philippe; <a href="/facts/Robert_Sedgewick_(computer_scientist)/f1lY2MFL">Sedgewick, Robert</a> (2009), <a href="/facts/Analytic_Combinatorics/Uu9sF1dp">Analytic Combinatorics</a>, Cambridge University Press, <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 978-0-521-89806-5</li>
<li><a href="https://www.encyclopediaofmath.org/index.php?title=Tree">"Tree"</a>, <a href="/facts/Encyclopedia_of_Mathematics/WC6mGtPm">Encyclopedia of Mathematics</a>, <a href="/facts/European_Mathematical_Society/B3h7b672">EMS Press</a>, 2001 [1994]</li>
<li><a href="/facts/Donald_E._Knuth/GozNzDM6">Knuth, Donald E.</a> (November 14, 1997), The Art of Computer Programming Volume 1: Fundamental Algorithms (3rd ed.), Addison-Wesley Professional</li>
<li>Jerrum, Mark (1994), "Counting trees in a graph is #P-complete", Information Processing Letters, 51 (3): 111–116, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1016%2F0020-0190%2894%2900085-9">10.1016/0020-0190(94)00085-9</a>, <a href="/facts/ISSN_(identifier)/DPAflDvU">ISSN</a> <a href="https://search.worldcat.org/issn/0020-0190">0020-0190</a>.</li>
<li>Otter, Richard (1948), "The Number of Trees", Annals of Mathematics, Second Series, 49 (3): 583–599, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.2307%2F1969046">10.2307/1969046</a>, <a href="/facts/JSTOR_(identifier)/YTeVmaJ7">JSTOR</a> <a href="https://www.jstor.org/stable/1969046">1969046</a>.</li></ul>

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

<ol>
<li id="fn:1">Bender & Williamson 2010, p. 171. - Bender, Edward A.; Williamson, S. Gill (2010), Lists, Decisions and Graphs. With an Introduction to Probability <a href="https://books.google.com/books?id=vaXv_yhefG8C" target="_blank">https://books.google.com/books?id=vaXv_yhefG8C</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
<li id="fn:2">Bender & Williamson 2010, p. 172. - Bender, Edward A.; Williamson, S. Gill (2010), Lists, Decisions and Graphs. With an Introduction to Probability <a href="https://books.google.com/books?id=vaXv_yhefG8C" target="_blank">https://books.google.com/books?id=vaXv_yhefG8C</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></li>
<li id="fn:3">Deo 1974, p. 206. - Deo, Narsingh (1974), Graph Theory with Applications to Engineering and Computer Science (PDF), Englewood, New Jersey: Prentice-Hall, ISBN 0-13-363473-6, archived (PDF) from the original on 2019-05-17 <a href="https://www.edutechlearners.com/download/Graphtheory.pdf" target="_blank">https://www.edutechlearners.com/download/Graphtheory.pdf</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></li>
<li id="fn:4">See Harary & Sumner (1980). - Harary, Frank; Sumner, David (1980), "The dichromatic number of an oriented tree", Journal of Combinatorics, Information & System Sciences, 5 (3): 184–187, MR 0603363 <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=0603363" target="_blank">https://mathscinet.ams.org/mathscinet-getitem?mr=0603363</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></li>
<li id="fn:5">See Simion (1991). - Simion, Rodica (1991), "Trees with 1-factors and oriented trees", Discrete Mathematics, 88 (1): 93–104, doi:10.1016/0012-365X(91)90061-6, MR 1099270 <a href="https://doi.org/10.1016%2F0012-365X%2891%2990061-6" target="_blank">https://doi.org/10.1016%2F0012-365X%2891%2990061-6</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></li>
<li id="fn:6">See Dasgupta (1999). - Dasgupta, Sanjoy (1999), "Learning polytrees", Proc. 15th Conference on Uncertainty in Artificial Intelligence (UAI 1999), Stockholm, Sweden, July–August 1999 (PDF), pp. 134–141 <a href="http://cseweb.ucsd.edu/~dasgupta/papers/poly.pdf" target="_blank">http://cseweb.ucsd.edu/~dasgupta/papers/poly.pdf</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></li>
<li id="fn:7">See Kim & Pearl (1983). - Kim, Jin H.; Pearl, Judea (1983), "A computational model for causal and diagnostic reasoning in inference engines", Proc. 8th International Joint Conference on Artificial Intelligence (IJCAI 1983), Karlsruhe, Germany, August 1983 (PDF), pp. 190–193 <a href="https://www.ijcai.org/Proceedings/83-1/Papers/041.pdf" target="_blank">https://www.ijcai.org/Proceedings/83-1/Papers/041.pdf</a> <a href="#fnref:7" class="footnote-back-ref">↩</a></li>
<li id="fn:8">Stanley Gill Williamson (1985). Combinatorics for Computer Science. Courier Dover Publications. p. 288. ISBN 978-0-486-42076-9. <a href="978-0-486-42076-9" target="_blank">978-0-486-42076-9</a> <a href="#fnref:8" class="footnote-back-ref">↩</a></li>
<li id="fn:9">Mehran Mesbahi; Magnus Egerstedt (2010). Graph Theoretic Methods in Multiagent Networks. Princeton University Press. p. 38. ISBN 978-1-4008-3535-5. <a href="978-1-4008-3535-5" target="_blank">978-1-4008-3535-5</a> <a href="#fnref:9" class="footnote-back-ref">↩</a></li>
<li id="fn:10">Deo 1974, p. 206. - Deo, Narsingh (1974), Graph Theory with Applications to Engineering and Computer Science (PDF), Englewood, New Jersey: Prentice-Hall, ISBN 0-13-363473-6, archived (PDF) from the original on 2019-05-17 <a href="https://www.edutechlearners.com/download/Graphtheory.pdf" target="_blank">https://www.edutechlearners.com/download/Graphtheory.pdf</a> <a href="#fnref:10" class="footnote-back-ref">↩</a></li>
<li id="fn:11">Ding-Zhu Du; Ker-I Ko; Xiaodong Hu (2011). Design and Analysis of Approximation Algorithms. Springer Science & Business Media. p. 108. ISBN 978-1-4614-1701-9. <a href="978-1-4614-1701-9" target="_blank">978-1-4614-1701-9</a> <a href="#fnref:11" class="footnote-back-ref">↩</a></li>
<li id="fn:12">Deo 1974, p. 207. - Deo, Narsingh (1974), Graph Theory with Applications to Engineering and Computer Science (PDF), Englewood, New Jersey: Prentice-Hall, ISBN 0-13-363473-6, archived (PDF) from the original on 2019-05-17 <a href="https://www.edutechlearners.com/download/Graphtheory.pdf" target="_blank">https://www.edutechlearners.com/download/Graphtheory.pdf</a> <a href="#fnref:12" class="footnote-back-ref">↩</a></li>
<li id="fn:13">Jonathan L. Gross; Jay Yellen; Ping Zhang (2013). Handbook of Graph Theory, Second Edition. CRC Press. p. 116. ISBN 978-1-4398-8018-0. <a href="978-1-4398-8018-0" target="_blank">978-1-4398-8018-0</a> <a href="#fnref:13" class="footnote-back-ref">↩</a></li>
<li id="fn:14">Bernhard Korte; Jens Vygen (2012). Combinatorial Optimization: Theory and Algorithms (5th ed.). Springer Science & Business Media. p. 28. ISBN 978-3-642-24488-9. <a href="978-3-642-24488-9" target="_blank">978-3-642-24488-9</a> <a href="#fnref:14" class="footnote-back-ref">↩</a></li>
<li id="fn:15">Deo 1974, p. 207. - Deo, Narsingh (1974), Graph Theory with Applications to Engineering and Computer Science (PDF), Englewood, New Jersey: Prentice-Hall, ISBN 0-13-363473-6, archived (PDF) from the original on 2019-05-17 <a href="https://www.edutechlearners.com/download/Graphtheory.pdf" target="_blank">https://www.edutechlearners.com/download/Graphtheory.pdf</a> <a href="#fnref:15" class="footnote-back-ref">↩</a></li>
<li id="fn:16">Kurt Mehlhorn; Peter Sanders (2008). Algorithms and Data Structures: The Basic Toolbox (PDF). Springer Science & Business Media. p. 52. ISBN 978-3-540-77978-0. Archived (PDF) from the original on 2015-09-08. <a href="978-3-540-77978-0" target="_blank">978-3-540-77978-0</a> <a href="#fnref:16" class="footnote-back-ref">↩</a></li>
<li id="fn:17">David Makinson (2012). Sets, Logic and Maths for Computing. Springer Science & Business Media. pp. 167–168. ISBN 978-1-4471-2499-3. <a href="978-1-4471-2499-3" target="_blank">978-1-4471-2499-3</a> <a href="#fnref:17" class="footnote-back-ref">↩</a></li>
<li id="fn:18">Kenneth Rosen (2011). Discrete Mathematics and Its Applications, 7th edition. McGraw-Hill Science. p. 747. ISBN 978-0-07-338309-5. <a href="978-0-07-338309-5" target="_blank">978-0-07-338309-5</a> <a href="#fnref:18" class="footnote-back-ref">↩</a></li>
<li id="fn:19">Alexander Schrijver (2003). Combinatorial Optimization: Polyhedra and Efficiency. Springer. p. 34. ISBN 3-540-44389-4. <a href="3-540-44389-4" target="_blank">3-540-44389-4</a> <a href="#fnref:19" class="footnote-back-ref">↩</a></li>
<li id="fn:20">Cayley (1857) "On the theory of the analytical forms called trees," Philosophical Magazine, 4th series, 13 : 172–176.However it should be mentioned that in 1847, K.G.C. von Staudt, in his book Geometrie der Lage (Nürnberg, (Germany): Bauer und Raspe, 1847), presented a proof of Euler's polyhedron theorem which relies on trees on pages 20–21. Also in 1847, the German physicist Gustav Kirchhoff investigated electrical circuits and found a relation between the number (n) of wires/resistors (branches), the number (m) of junctions (vertices), and the number (μ) of loops (faces) in the circuit. He proved the relation via an argument relying on trees. See: Kirchhoff, G. R. (1847) "Ueber die Auflösung der Gleichungen, auf welche man bei der Untersuchung der linearen Vertheilung galvanischer Ströme geführt wird" Archived 2023-07-20 at the Wayback Machine (On the solution of equations to which one is led by the investigation of the linear distribution of galvanic currents), Annalen der Physik und Chemie, 72 (12) : 497–508. <a href="https://books.google.com/books?id=MlEEAAAAYAAJ&pg=PA172" target="_blank">https://books.google.com/books?id=MlEEAAAAYAAJ&pg=PA172</a> <a href="#fnref:20" class="footnote-back-ref">↩</a></li>
<li id="fn:21">DeBiasio, Louis; Lo, Allan (2019-10-09). "Spanning trees with few branch vertices". arXiv:1709.04937 [math.CO]. <a href="/wiki/ArXiv_(identifier)" target="_blank">/wiki/ArXiv_(identifier)</a> <a href="#fnref:21" class="footnote-back-ref">↩</a></li>
<li id="fn:22">Harary & Prins 1959, p. 150. - Harary, Frank; Prins, Geert (1959), "The number of homeomorphically irreducible trees, and other species", Acta Mathematica, 101 (1–2): 141–162, doi:10.1007/BF02559543, ISSN 0001-5962 <a href="https://projecteuclid.org/euclid.acta/1485889061" target="_blank">https://projecteuclid.org/euclid.acta/1485889061</a> <a href="#fnref:22" class="footnote-back-ref">↩</a></li>
<li id="fn:23">See Dasgupta (1999). - Dasgupta, Sanjoy (1999), "Learning polytrees", Proc. 15th Conference on Uncertainty in Artificial Intelligence (UAI 1999), Stockholm, Sweden, July–August 1999 (PDF), pp. 134–141 <a href="http://cseweb.ucsd.edu/~dasgupta/papers/poly.pdf" target="_blank">http://cseweb.ucsd.edu/~dasgupta/papers/poly.pdf</a> <a href="#fnref:23" class="footnote-back-ref">↩</a></li>
<li id="fn:24">Deo 1974, p. 206. - Deo, Narsingh (1974), Graph Theory with Applications to Engineering and Computer Science (PDF), Englewood, New Jersey: Prentice-Hall, ISBN 0-13-363473-6, archived (PDF) from the original on 2019-05-17 <a href="https://www.edutechlearners.com/download/Graphtheory.pdf" target="_blank">https://www.edutechlearners.com/download/Graphtheory.pdf</a> <a href="#fnref:24" class="footnote-back-ref">↩</a></li>
<li id="fn:25">See Harary & Sumner (1980). - Harary, Frank; Sumner, David (1980), "The dichromatic number of an oriented tree", Journal of Combinatorics, Information & System Sciences, 5 (3): 184–187, MR 0603363 <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=0603363" target="_blank">https://mathscinet.ams.org/mathscinet-getitem?mr=0603363</a> <a href="#fnref:25" class="footnote-back-ref">↩</a></li>
<li id="fn:26">See Simion (1991). - Simion, Rodica (1991), "Trees with 1-factors and oriented trees", Discrete Mathematics, 88 (1): 93–104, doi:10.1016/0012-365X(91)90061-6, MR 1099270 <a href="https://doi.org/10.1016%2F0012-365X%2891%2990061-6" target="_blank">https://doi.org/10.1016%2F0012-365X%2891%2990061-6</a> <a href="#fnref:26" class="footnote-back-ref">↩</a></li>
<li id="fn:27">See Kim & Pearl (1983). - Kim, Jin H.; Pearl, Judea (1983), "A computational model for causal and diagnostic reasoning in inference engines", Proc. 8th International Joint Conference on Artificial Intelligence (IJCAI 1983), Karlsruhe, Germany, August 1983 (PDF), pp. 190–193 <a href="https://www.ijcai.org/Proceedings/83-1/Papers/041.pdf" target="_blank">https://www.ijcai.org/Proceedings/83-1/Papers/041.pdf</a> <a href="#fnref:27" class="footnote-back-ref">↩</a></li>
<li id="fn:28">Chen, Wai-kai (1966). "On directed trees and directed k-trees of a digraph and their generation". SIAM Journal on Applied Mathematics. 14 (3): 550–560. doi:10.1137/0114048. MR 0209064. <a href="/wiki/SIAM_Journal_on_Applied_Mathematics" target="_blank">/wiki/SIAM_Journal_on_Applied_Mathematics</a> <a href="#fnref:28" class="footnote-back-ref">↩</a></li>
<li id="fn:29">Kozlov, Dmitry N. (1999). "Complexes of directed trees". Journal of Combinatorial Theory. Series A. 88 (1): 112–122. doi:10.1006/jcta.1999.2984. MR 1713484. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:29" class="footnote-back-ref">↩</a></li>
<li id="fn:30">Tran, Ngoc Mai; Buck, Johannes; Klüppelberg, Claudia (February 2024), "Estimating a directed tree for extremes", Journal of the Royal Statistical Society Series B: Statistical Methodology, 86 (3): 771–792, arXiv:2102.06197, doi:10.1093/jrsssb/qkad165 <a href="/wiki/ArXiv_(identifier)" target="_blank">/wiki/ArXiv_(identifier)</a> <a href="#fnref:30" class="footnote-back-ref">↩</a></li>
<li id="fn:31">Kozlov, Dmitry N. (1999). "Complexes of directed trees". Journal of Combinatorial Theory. Series A. 88 (1): 112–122. doi:10.1006/jcta.1999.2984. MR 1713484. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:31" class="footnote-back-ref">↩</a></li>
<li id="fn:32">Bender & Williamson 2010, p. 173. - Bender, Edward A.; Williamson, S. Gill (2010), Lists, Decisions and Graphs. With an Introduction to Probability <a href="https://books.google.com/books?id=vaXv_yhefG8C" target="_blank">https://books.google.com/books?id=vaXv_yhefG8C</a> <a href="#fnref:32" class="footnote-back-ref">↩</a></li>
<li id="fn:33">Deo 1974, p. 206. - Deo, Narsingh (1974), Graph Theory with Applications to Engineering and Computer Science (PDF), Englewood, New Jersey: Prentice-Hall, ISBN 0-13-363473-6, archived (PDF) from the original on 2019-05-17 <a href="https://www.edutechlearners.com/download/Graphtheory.pdf" target="_blank">https://www.edutechlearners.com/download/Graphtheory.pdf</a> <a href="#fnref:33" class="footnote-back-ref">↩</a></li>
<li id="fn:34">Deo 1974, p. 207. - Deo, Narsingh (1974), Graph Theory with Applications to Engineering and Computer Science (PDF), Englewood, New Jersey: Prentice-Hall, ISBN 0-13-363473-6, archived (PDF) from the original on 2019-05-17 <a href="https://www.edutechlearners.com/download/Graphtheory.pdf" target="_blank">https://www.edutechlearners.com/download/Graphtheory.pdf</a> <a href="#fnref:34" class="footnote-back-ref">↩</a></li>
<li id="fn:35">Deo 1974, p. 207. - Deo, Narsingh (1974), Graph Theory with Applications to Engineering and Computer Science (PDF), Englewood, New Jersey: Prentice-Hall, ISBN 0-13-363473-6, archived (PDF) from the original on 2019-05-17 <a href="https://www.edutechlearners.com/download/Graphtheory.pdf" target="_blank">https://www.edutechlearners.com/download/Graphtheory.pdf</a> <a href="#fnref:35" class="footnote-back-ref">↩</a></li>
<li id="fn:36">Bender & Williamson 2010, p. 173. - Bender, Edward A.; Williamson, S. Gill (2010), Lists, Decisions and Graphs. With an Introduction to Probability <a href="https://books.google.com/books?id=vaXv_yhefG8C" target="_blank">https://books.google.com/books?id=vaXv_yhefG8C</a> <a href="#fnref:36" class="footnote-back-ref">↩</a></li>
<li id="fn:37">Bender & Williamson 2010, p. 173. - Bender, Edward A.; Williamson, S. Gill (2010), Lists, Decisions and Graphs. With an Introduction to Probability <a href="https://books.google.com/books?id=vaXv_yhefG8C" target="_blank">https://books.google.com/books?id=vaXv_yhefG8C</a> <a href="#fnref:37" class="footnote-back-ref">↩</a></li>
<li id="fn:38">Bender & Williamson 2010, p. 173. - Bender, Edward A.; Williamson, S. Gill (2010), Lists, Decisions and Graphs. With an Introduction to Probability <a href="https://books.google.com/books?id=vaXv_yhefG8C" target="_blank">https://books.google.com/books?id=vaXv_yhefG8C</a> <a href="#fnref:38" class="footnote-back-ref">↩</a></li>
<li id="fn:39">Bender & Williamson 2010, p. 173. - Bender, Edward A.; Williamson, S. Gill (2010), Lists, Decisions and Graphs. With an Introduction to Probability <a href="https://books.google.com/books?id=vaXv_yhefG8C" target="_blank">https://books.google.com/books?id=vaXv_yhefG8C</a> <a href="#fnref:39" class="footnote-back-ref">↩</a></li>
<li id="fn:40">Bender & Williamson 2010, p. 173. - Bender, Edward A.; Williamson, S. Gill (2010), Lists, Decisions and Graphs. With an Introduction to Probability <a href="https://books.google.com/books?id=vaXv_yhefG8C" target="_blank">https://books.google.com/books?id=vaXv_yhefG8C</a> <a href="#fnref:40" class="footnote-back-ref">↩</a></li>
<li id="fn:41">See Black, Paul E. (4 May 2007). "k-ary tree". U.S. National Institute of Standards and Technology. Archived from the original on 8 February 2015. Retrieved 8 February 2015. <a href="http://xlinux.nist.gov/dads/HTML/karyTree.html" target="_blank">http://xlinux.nist.gov/dads/HTML/karyTree.html</a> <a href="#fnref:41" class="footnote-back-ref">↩</a></li>
<li id="fn:42">Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2022). Introduction to Algorithms (4th ed.). Section B.5.3, Binary and positional trees: MIT Press. p. 1174. ISBN 9780262046305. Archived from the original on 16 July 2023. Retrieved 20 July 2023.{{cite book}}: CS1 maint: location (link) <a href="9780262046305" target="_blank">9780262046305</a> <a href="#fnref:42" class="footnote-back-ref">↩</a></li>
<li id="fn:43">Bender & Williamson 2010, p. 173. - Bender, Edward A.; Williamson, S. Gill (2010), Lists, Decisions and Graphs. With an Introduction to Probability <a href="https://books.google.com/books?id=vaXv_yhefG8C" target="_blank">https://books.google.com/books?id=vaXv_yhefG8C</a> <a href="#fnref:43" class="footnote-back-ref">↩</a></li>
<li id="fn:44">Stanley, Richard P. (2012), Enumerative Combinatorics, Vol. I, Cambridge Studies in Advanced Mathematics, vol. 49, Cambridge University Press, p. 573, ISBN 9781107015425 <a href="9781107015425" target="_blank">9781107015425</a> <a href="#fnref:44" class="footnote-back-ref">↩</a></li>
<li id="fn:45">Diestel (2005), Prop. 8.2.4. - Diestel, Reinhard (2005), Graph Theory (3rd ed.), Berlin, New York: Springer-Verlag, ISBN 978-3-540-26183-4 <a href="http://diestel-graph-theory.com/index.html" target="_blank">http://diestel-graph-theory.com/index.html</a> <a href="#fnref:45" class="footnote-back-ref">↩</a></li>
<li id="fn:46">Diestel (2005), Prop. 8.5.2. - Diestel, Reinhard (2005), Graph Theory (3rd ed.), Berlin, New York: Springer-Verlag, ISBN 978-3-540-26183-4 <a href="http://diestel-graph-theory.com/index.html" target="_blank">http://diestel-graph-theory.com/index.html</a> <a href="#fnref:46" class="footnote-back-ref">↩</a></li>
<li id="fn:47">See Li (1996). - Li, Gang (1996), "Generation of Rooted Trees and Free Trees", M.S. Thesis, Dept. of Computer Science, University of Victoria, BC, Canada (PDF), p. 9 <a href="http://webhome.cs.uvic.ca/~ruskey/Theses/GangLiMScThesis.pdf" target="_blank">http://webhome.cs.uvic.ca/~ruskey/Theses/GangLiMScThesis.pdf</a> <a href="#fnref:47" class="footnote-back-ref">↩</a></li>
</ol>

Tree (graph theory) open-in-new

Tree (graph theory)