Trees

n−1 edges, unique paths, spanning trees, and the MST.

The idea

Definition (Tree).

A tree is a connected graph with no cycles: every vertex can be reached from every other, and no route returns to its starting vertex without reusing an edge.

Hierarchies, file systems and network backbones are all trees.

Theorem (Characterizations of a tree).

For a graph $G$ on $n$ vertices the following are equivalent: $G$ is connected and has no cycles; $G$ is connected and has exactly $n - 1$ edges; every pair of vertices of $G$ is joined by exactly one path.

Each characterization is useful in its own place. The count $n - 1$ is also minimal — deleting any edge of a tree disconnects it into two pieces, while adding any edge closes a cycle.

A spanning tree of a connected graph is a tree that uses all of the graph's vertices: the fewest edges that keep every vertex connected to every other.

Ways to work on it

• Walkthrough. Tree facts: n−1 edges, unique paths, spanning trees.
• Proof. Why a tree on n vertices has exactly n−1 edges (induction).
• Practice. Relate a tree's vertices and edges.
• Hardest. Build a minimum spanning tree of a weighted graph.

Not sure where to start? Take the ten-question placement test.