  ## Encyclopedia > Tree (graph theory)

Article Content

# Tree (graph theory)

In graph theory, a tree is a graph in which, roughly speaking, any two vertices are connected by a single path.

An undirected simple graph G is called 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

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 nn-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

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

All Wikipedia text is available under the terms of the GNU Free Documentation License

Search Encyclopedia
 Search over one million articles, find something about almost anything!

Featured Article
 Father Damien ... priest who dedicated his life to ministering to the sufferers of Hansen's disease (leprosy) who lived on the island of Molokai, Hawaii. He was born in Tremeloo, ...  