Tree (graph theory)

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



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

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


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 planar and bipartite 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 nn−2 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 d1,d2,...,dn is

<math> {n-2 \choose d_1-1, d_2-1, \ldots, d_n-1},<math>

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

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

Types of trees

See List of graph theory topics: Trees.

Related articles

de:W鋖der und B鋟me in der Graphentheorie he:עץ (תורת הגרפים) it:albero (grafo) ja:木 (数学) lt:Medis (grafų teorija) pl:drzewo (matematyka) fi:puu (graafiteoria) th:ต้นไม้ (ทฤษฎีกราฟ) zh:树_(图论)


  • Art and Cultures
    • Art (
    • Architecture (
    • Cultures (
    • Music (
    • Musical Instruments (
  • Biographies (
  • Clipart (
  • Geography (
    • Countries of the World (
    • Maps (
    • Flags (
    • Continents (
  • History (
    • Ancient Civilizations (
    • Industrial Revolution (
    • Middle Ages (
    • Prehistory (
    • Renaissance (
    • Timelines (
    • United States (
    • Wars (
    • World History (
  • Human Body (
  • Mathematics (
  • Reference (
  • Science (
    • Animals (
    • Aviation (
    • Dinosaurs (
    • Earth (
    • Inventions (
    • Physical Science (
    • Plants (
    • Scientists (
  • Social Studies (
    • Anthropology (
    • Economics (
    • Government (
    • Religion (
    • Holidays (
  • Space and Astronomy
    • Solar System (
    • Planets (
  • Sports (
  • Timelines (
  • Weather (
  • US States (


  • Home Page (
  • Contact Us (

  • Clip Art (
Personal tools