Tree (graph theory)

A labeled tree with 6 vertices and 5 edges

In graph theory, a tree is a graph in which any two vertices are connected by exactly one path. A forest is a graph in which any two vertices are connected by at most one path. An equivalent definition is that a forest is a disjoint union of trees (hence the name). Trees are widely used in Computer Science data structures such as binary search trees, heaps, tries, etc.

Definitions

A tree is an undirected simple graph G that satisfies any of the following equivalent conditions:

• G is connected and has no simple cycles.
• G has no simple cycles, and a simple cycle is formed if any edge is added to G.
• G is connected, and it is not connected anymore if any edge is removed from G.
• G is connected and the 3-vertex complete graph $K_{3}$ is not a minor of G.
• Any two vertices in G can be connected by a unique simple path.

If G has finitely many vertices, say n of them, then the above statements are also equivalent to any of the following conditions:

• G is connected and has n − 1 edges.
• G has no simple cycles and has n − 1 edges.
• G has n − 1 distinct edges.

An undirected simple graph G is called a forest if it has no simple cycles.

A directed tree is a directed graph which would be a tree if the directions on the edges were ignored. Some authors restrict the phrase to the case where the edges are all directed towards a particular vertex, or all directed away from a particular vertex.

A tree is called a rooted tree if one vertex has been designated the root, in which case the edges have a natural orientation, towards or away from the root. Rooted trees, often with additional structure such as ordering of the neighbors at each vertex, are a key data structure in computer science; see tree data structure. 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 are typically given the labels 1, 2, …, n.

A regular (or homogeneous) tree is a tree in which every vertex has the same degree. See regular graph.

An irreducible (or series-reduced) tree is a tree in which there is no vertex of degree 2.

Example

The example tree shown to the right has 6 vertices and 6 − 1 = 5 edges. The unique simple path connecting the vertices 2 and 6 is 2-4-5-6.

Facts

• Every tree is a bipartite graph. Every tree with only countably many vertices is a planar graph.

• Every connected graph G admits a spanning tree, which is a tree that contains every vertex of G and whose edges are edges of G.

• Given n labeled vertices, there are nⁿ⁻² different ways to connect them to make a tree. This result is called Cayley's formula.

• The number of trees with n vertices of degree d₁,d₂,...,d_n is

${n-2 \choose d_{1}-1,d_{2}-1,\ldots ,d_{n}-1},$

which is a multinomial coefficient.

• No closed formula for the number t(n) of trees with n vertices up to graph isomorphism is known. However, the asymptotic behavior of t(n) is known: there are numbers α ≈ 3 and β ≈ 0.5 such that

$\lim _{n\to \infty }{\frac {t(n)}{\beta \alpha ^{n}n^{-5/2}}}=1.$

Types of trees

See List of graph theory topics: Trees.

See also

• Tree structure
• Tree data structure
• Binary tree