A tree is a finite simple graph with at least one graph vertex that is undirected, connected, and acyclic (or, equivalently, a connected forest). Tree data structures typically also specify a root vertex and may order the children of each graph vertex; their underlying graphs are trees.
Cayley (1857) studied trees. McKay maintains a database of trees up to 22 vertices, and Royle maintains one up to 20 vertices.
A tree with 
nodes
has 
graph edges.
Conversely, a connected graph with 
nodes and 
edges is a tree. All trees
are bipartite graphs (Skiena 1990, p. 213).
Trees with no particular node singled out are called
unrooted trees, also known as free trees, by way
of distinguishing them from rooted trees (Skiena 1990,
Knuth 1997).
The vertices of vertex degree 1 in an unrooted tree are called tree leaves. A binary tree is a rooted tree structure in which each graph vertex has at most two children, designated as its left and right children.
A graph can be tested in the Wolfram Language to see if it is a tree using TreeGraphQ[g].
Trees find applications in many diverse fields, including computer science, the enumeration of saturated hydrocarbons, the study of electrical circuits, etc. (Harary 1994, p. 4). The graphs corresponding to linear hydrocarbons illustrated above are known as (n-)alkane graphs (or sometimes caterpillar graphs).
Trees are block graphs.
A tree 
has either one node
that is a graph center, in which case it is called
a centered tree, or two adjacent nodes that are graph centers,
in which case it is called a bicentered tree (Harary
1994, p. 35).
When a special node is designated to turn a tree into a rooted tree, it is called the root (or sometimes "Eve"). A child of a graph vertex is an adjacent graph vertex whose graph distance from the root vertex is one greater. Distinct children of the same graph vertex are called siblings.
There is only one tree of order 3 up to graph isomorphism, namely the path graph 
. The number 
of nonisomorphic trees
of order 
, 2, ... (where trees of orders
1, 2, ..., 6 are illustrated above), are 1, 1, 1, 2, 3, 6, 11, 23, 47, 106, 235,
551, 1301, 3159, ... (OEIS A000055).
The ordinary generating function for the number of rooted trees, counted up to root-preserving graph isomorphism without an ordering of the children,
 |  |  |
(1)
|
 |  | ![xexp[sum_(r=1)^(infty)1/rT(x^r)]](/images/equations/Tree/Inline14.svg) |
(2)
|
is related to the generating function for the number of unrooted trees 
by
 |  |  |
(3)
|
 |  | ![T(x)-1/2[T^2(x)-T(x^2)].](/images/equations/Tree/Inline21.svg) |
(4)
|
Otter (1948) showed that
 |
(5)
|
(Otter 1948, Harary and Palmer 1973, Knuth 1997), where 
and 
are two constants. 
is given by
 |  |  |
(6)
|
 |  |  |
(7)
|
(OEIS A051491; Odlyzko 1995; Knuth 1997, p. 396, where Knuth writes 
instead of 
) and also as the unique
positive root of
 |
(8)
|
The constant 
is given by
 |  | ![1/(sqrt(2pi))[1+sum_(k=2)^(infty)T^'(1/(alpha^k))1/(alpha^k)]^(3/2)](/images/equations/Tree/Inline36.svg) |
(9)
|
 |  |  |
(10)
|
(OEIS A086308; Plotkin and Rosenthal 1994, p. 140; Knuth 1997, p. 396).
If 
is the number of nonisomorphic
trees on 
nodes,
then an asymptotic series for 
is given by
 |
(11)
|
where the constants can be computed in terms of partial derivatives of the function
![F(x,y)=xexp[y+sum_(k=2)^infty(T(x^k))/k]-y](/images/equations/Tree/NumberedEquation4.svg) |
(12)
|
(Plotkin and Rosenthal 1994, p. 140; Finch 2003, p. 2).
