Trees

Definition

Tree

A tree is a connected graph with no cycles. Equivalently, a tree on n vertices has exactly n - 1 edges, and there is a unique path between every pair of vertices.

A forest is a graph with no cycles (a disjoint union of trees).

Theorem

Properties of Trees

For a graph G with n vertices, the following are equivalent: 1. G is a tree (connected and acyclic). 2. G is connected and has n - 1 edges. 3. G is acyclic and has n - 1 edges. 4. There is exactly one path between every pair of vertices. 5. G is connected, but removing any edge disconnects it. 6. G is acyclic, but adding any edge creates exactly one cycle.

Definition

Rooted Tree Terminology

In a rooted tree, one vertex is designated as the root. • Parent of v: the vertex on the path from v to the root. • Children of v: vertices whose parent is v. • Leaf: a vertex with no children. • Internal vertex: a vertex with at least one child. • Depth of v: length of the path from the root to v. • Height of tree: maximum depth of any vertex.

Definition

Spanning Tree

A spanning tree of a connected graph G is a subgraph that is a tree and includes every vertex of G. Every connected graph has at least one spanning tree.

A minimum spanning tree (MST) of a weighted graph is a spanning tree whose total edge weight is minimized.

Example

Counting Spanning Trees

The complete graph K₄ has 4⁴⁻² = 16 spanning trees (by Cayley's formula: Kₙ has nⁿ⁻² spanning trees).

K₃ has 3¹ = 3 spanning trees - each is obtained by removing one of the 3 edges from the triangle.

Definition

Binary Tree

A binary tree is a rooted tree where each vertex has at most 2 children (left child and right child).

A full binary tree has every internal vertex with exactly 2 children.

A binary tree of height h has at most 2ʰ⁺¹ - 1 vertices and at most 2ʰ leaves.