# Tree (graph theory)

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

An undirected simple graph *G* is a *tree* if it satisfies one (and therefore all) of the following equivalent conditions:

*G* is connected and has no simple cycles
*G* has no simple cycles and, if any edge is added to *G*, then a simple cycle is formed
*G* is connected and, if any edge is removed from *G*, then it is not connected anymore
- 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:

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

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 planar and bipartite.

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* different vertices, there are *n*^{n-2} different ways to connect them to make a tree. 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

## Types of Trees

See also

Tree structure,

Tree data structure.