Tree (graph theory)

[1] A forest is an undirected graph in which any two vertices are connected by at most one path, or equivalently an acyclic undirected graph, or equivalently a disjoint union of trees.

The term tree was coined in 1857 by the British mathematician Arthur Cayley.

[20] A forest is an undirected acyclic graph or equivalently a disjoint union of trees.

[11] The tree-order is the partial ordering on the vertices of a tree with u < v if and only if the unique path from the root to v passes through u.

[24][27] 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.

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.

A classic proof uses Prüfer sequences, which naturally show a stronger result: the number of trees with vertices 1, 2, …, n of degrees d1, d2, …, dn respectively, is the multinomial coefficient A more general problem is to count spanning trees in an undirected graph, which is addressed by the matrix tree theorem.

(Cayley's formula is the special case of spanning trees in a complete graph.)

The similar problem of counting all the subtrees regardless of size is #P-complete in the general case (Jerrum (1994)).

Counting the number of unlabeled free trees is a harder problem.

No closed formula for the number t(n) of trees with n vertices up to graph isomorphism is known.

The first few values of t(n) are Otter (1948) proved the asymptotic estimate with C ≈ 0.534949606... and α ≈ 2.95576528565... (sequence A051491 in the OEIS).

Here, the ~ symbol means that This is a consequence of his asymptotic estimate for the number r(n) of unlabeled rooted trees with n vertices: with D ≈ 0.43992401257... and the same α as above (cf.