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 1 Definitions 2 Example 3 Facts 4 Types of Trees

Definitions

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

Example

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.

Facts

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

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

Types of Trees

• Free tree[?]
• Rooted tree[?]
  • Ordered tree[?]
• Binary tree
  • Full binary tree[?]
• Positional tree[?]
• Empty tree[?]
• K-ary tree[?]
• Charles' tree[?]

See also Tree structure.