Trees

Trees are the simplest connected graphs and the backbone of many data structures.

Definition

Equivalent Properties

For a graph $T$ with $n$ vertices, the following are equivalent:

1. $T$ is a tree.
2. $T$ is connected and has $n-1$ edges.
3. $T$ has no cycles and has $n-1$ edges.
4. There is a unique path between any two vertices.

Spanning Trees

Every connected graph $G$ contains a spanning tree (a subgraph that is a tree and includes all vertices of $G$).

• Cayley's Formula: There are $n^{n-2}$ distinct labeled trees on $n$ vertices.

Leaves

Every tree with $n\ge 2$ vertices has at least two leaves (vertices of degree 1).

Practice Problems