Trees and Their Properties

In graph theory, trees represent one of the most vital subclasses of graphs, offering elegant mathematical structures and highly efficient algorithmic properties. This guide explores the formal definitions, theorems, and traversal behaviors of both free and rooted trees.

text

       [Free Tree]                    [Rooted Tree (Root = A)]
         1---2---3                              (A)  <-- Level 0
             |                                 /   \
             4                                (B)   (C)  <-- Level 1
            / \                              /   \
           5   6                           (D)   (E)  <-- Level 2

1. Fundamental Definitions and Structural Properties

A tree is formally defined as an undirected simple graph $T = (V, E)$ that is both connected and acyclic (contains no cycles). A forest is a collection of one or more disjoint trees.

Properties and Characterization Theorems

Trees possess highly restrictive topological configurations. The following mathematical equivalences define a tree:

The Unique Path Theorem: An undirected graph $G$ is a tree if and only if there is a unique simple path between any two of its vertices.
The Edge-Vertex Theorem: An undirected tree $T$ with $n$ vertices has exactly $n - 1$ edges: $|E| = |V| - 1$

Proof Sketch: Edge-Vertex Theorem (by Induction)

Let $P(n)$ be the statement that a tree with $n$ vertices has $n - 1$ edges.

Base Case ( $n = 1$ ): A tree with 1 vertex has 0 edges. Since $1 - 1 = 0$ , the base case holds.
Inductive Step: Assume $P(k)$ is true for all trees with $k$ vertices, where $k \ge 1$ . Let be a tree with vertices. Removing any edge from splits the tree into exactly two disjoint components, and , because contains no cycles. Since and are connected and acyclic, both are trees. Let and such that . Because , we can apply the inductive hypothesis: The total number of edges in is the sum of the edges in its subtrees plus the removed edge : Thus, is true, completing the proof.

2. Rooted Trees and Hierarchical Terminology

A rooted tree is a tree in which one vertex is designated as the root, and all edges are implicitly directed away from this root.

text

                  (Root: A)          [Level 0]
                   /     \
                 (B)     (C)         [Level 1]
                /   \       \
              (D)   (E)     (F)      [Level 2]

Hierarchical Vocabulary

Parent: The vertex $u$ immediately preceding vertex $v$ on the unique path from the root to $v$ . Here, $A$ is the parent of $B$ and $C$ .
Child: A vertex $v$ is a child of if is the parent of . and are children of .

3. $m$ -ary Trees and Binary Trees

Rooted trees are categorized by their branching factor.

Ordered Rooted Tree: A rooted tree where the children of each internal node are assigned a specific order (typically drawn left-to-right).
$m$ -ary Tree: A rooted tree where every internal node has at most $m$ children.
Full $m$ -ary Tree: A rooted tree where every internal node has exactly $m$ children.
Binary Tree: A 2-ary tree (each internal node has at most 2 children: a designated left child and right child). A full binary tree has every internal node with exactly 2 children.

text

        [Full Binary Tree]               [Non-Full Binary Tree]
               (A)                                (A)
              /   \                              /   \
            (B)   (C)                          (B)   (C)
           /   \                               /
         (D)   (E)                           (D)

Core Algebraic Formulas

For any full $m$ -ary tree, let:

$n$ be the total number of vertices
$i$ be the number of internal vertices
$L$ be the number of leaves

These variables are constrained by the following structural formulas:

Total Vertices: $n = m \cdot i + 1$
Leaf Count: $L = (m - 1)i + 1$
Internal Vertices from Total: $i = \frac{n - 1}{m}$

4. Tree Traversal Algorithms

For ordered rooted trees, we must often visit each vertex systematically. The three classic depth-first traversal algorithms are defined recursively:

text

          (Root)
          /    \
     [Left]    [Right]

Preorder Traversal (Node-Left-Right)

Visit the root.
Traverse the left subtree.
Traverse the right subtree.

Inorder Traversal (Left-Node-Right)

Traverse the left subtree.
Visit the root.
Traverse the right subtree.

Postorder Traversal (Left-Right-Node)

Traverse the left subtree.
Traverse the right subtree.
Visit the root.

Trace Example

Given the following ordered binary tree:

text

            (A)
           /   \
         (B)   (C)
        /   \
      (D)   (E)

5. Reachability and Node Bases in Directed Graphs

The structural properties of directed hierarchies depend on how nodes transition and reach one another.

Reachable Set $R(v)$ : In a directed graph (digraph) $G$ , the reachable set $R(v)$ of a node $v$ is the set of all vertices $u$ such that a directed path exists from $v$ to .

Essential Properties of a Node Base

A subset $S$ constitutes a node base if and only if it satisfies the following mathematical conditions:

Zero-Indegree Inclusion: $S$ must contain all nodes in the graph that have an indegree of $0$ . Since no path can enter these nodes, they cannot be reached from any external vertex.
Isolated Node Inclusion: $S$ must contain all isolated vertices (nodes with no incident edges).
Minimality: No vertex $u \in S$ is reachable from any other vertex $v \in S$ . If were reachable from , then could be removed from without losing coverage, violating the minimality condition.

Summary

Trees are connected, acyclic simple graphs. A tree with $n$ vertices always contains $n - 1$ edges.
The Unique Path Property states that a graph is a tree if and only if there is a unique simple path between every pair of vertices.
Rooted trees establish hierarchical networks. A full $m$ -ary tree ensures each internal node has exactly $m$ children, governed by the invariant $n = m \cdot i + 1$ .

Assessed progress

Trees and Their Properties

Trees and Their Properties

1. Fundamental Definitions and Structural Properties

Properties and Characterization Theorems

Proof Sketch: Edge-Vertex Theorem (by Induction)

2. Rooted Trees and Hierarchical Terminology

Hierarchical Vocabulary

3. $m$ -ary Trees and Binary Trees

Core Algebraic Formulas

4. Tree Traversal Algorithms

Preorder Traversal (Node-Left-Right)

Inorder Traversal (Left-Node-Right)

Postorder Traversal (Left-Right-Node)

Trace Example

5. Reachability and Node Bases in Directed Graphs

Essential Properties of a Node Base

Summary

Key Concepts

Tree

Rooted Tree

m-ary Tree

Unique Simple Path Theorem

Tree Traversals

Quick Check

Discrete Mathematical Structures

Discrete Mathematical Structures