From Wikipedia, the free encyclopedia

Tree
A labeled tree with 6 vertices and 5 edges
Vertices	v
Edges	v - 1
Chromatic number	2

In graph theory, a tree is a graph in which any two vertices are connected by exactly one path. Alternatively, any connected graph with no cycles is a tree. A forest is a disjoint union of trees. Trees are widely used in computer science data structures such as binary search trees, heaps, tries, Huffman trees for data compression, etc.

Contents 1 Definitions 2 Example 3 Facts 4 Enumeration 5 Types of trees 6 See also 7 References

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₃ 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.

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. 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. A tree which is a subgraph of some graph G is a normal tree if the ends of every edge in G are comparable in this tree-order (Diestel 2005, p. 15). 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. In a context where trees are supposed to have a root, a tree without any designated root is called a free tree.

A polytree has at most one undirected path between any two vertices. In other words, a polytree is a directed acyclic graph (DAG) for which there are no undirected cycles either.

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.

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

An ordered tree is a tree for which an ordering is specified for the children of each node.

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.

• 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. Every connected graph even admits a normal spanning tree (Diestel 2005, Prop. 1.5.6).

• Every tree with vertices has at least two leaves or vertices of degree 1. The minimal number of leaves corresponds to path tree but maximal number (n − 1) corresponds to star graph.

• For any three vertices in a tree, the three paths between them have at least one vertex in common.

Given n labeled vertices, there are nⁿ⁻² different ways to connect them to make a tree. This result is called Cayley's formula. It can be proved by first showing that the number of trees with n vertices of degree d₁,d₂,...,d_n is the multinomial coefficient

Counting the number of unlabeled trees is a harder problem. No closed formula for the number t(n) of trees with n vertices up to graph isomorphism is known. Otter (1948) proved that

with C = 0.53495… and α = 2.95576… (here, f ∼ g means that lim f/g = 1).

See List of graph theory topics: Trees.

• Tree structure
• Tree data structure
• Binary tree
• Pseudoforest

• Diestel, Reinhard (2005), Graph Theory (3rd ed.), Berlin, New York: Springer-Verlag, ISBN 978-3-540-26183-4, <http://www.math.uni-hamburg.de/home/diestel/books/graph.theory/>.
• Otter, Richard (1948), "The Number of Trees", Annals of Mathematics, Second Series 49 (3): 583–599, DOI 10.2307/1969046.