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.

Table of contents


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

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

Types of Trees

See also Tree structure.

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
List of rare diseases starting with A

... of[?] Acyl-CoA dehydrogenase, very long chain, deficiency of[?] Acyl-CoA oxidase deficiency[?] Adactylia unilateral dominant[?] Adam complex familial[?] Adams ...

This page was created in 54.8 ms