A tree is a connected acyclic graph. Equivalently, a tree is a connected graph where removing any edge disconnects it, or a graph where there is exactly one path between any pair of vertices.

A forest is a graph where each connected component is a tree (an acyclic graph).

A leaf is a vertex of degree 1. An internal vertex has degree at least 2.

A rooted tree is a tree with one designated vertex called the root. This induces a parent-child relationship: for any vertex $v \neq root$, its parent is the unique vertex on the path from $v$ to the root. Vertices with the same parent are siblings. A vertex with no children is a leaf.

The height of a vertex is its distance from the root. The depth or level is the same as height. The height of the tree is the maximum height among all vertices.

A binary tree is a rooted tree where each vertex has at most two children (designated as left and right).

A spanning tree of a connected graph $G$ is a subgraph that is a tree and includes all vertices of $G$.

Every connected graph has at least one spanning tree (found by BFS or DFS). The minimum spanning tree (MST) problem asks for a spanning tree with minimum total edge weight.

Famous MST algorithms include:

• Kruskal's algorithm: Sort edges by weight, add edges if they don't create cycles
• Prim's algorithm: Grow tree from a starting vertex, always adding the minimum-weight edge connecting tree to non-tree vertices
• Borůvka's algorithm: Repeatedly find minimum-weight edge for each component and merge components

The number of labeled trees on $n$ vertices is $n^{n-2}$.

For example, there are $3^{3-2} = 3$ labeled trees on 3 vertices (the three distinct ways to connect vertices 1, 2, 3 as a path).

This can be proven using Prüfer sequences: bijection between labeled trees and sequences of length $n-2$ with entries from $\{1, \ldots, n\}$, giving $n^{n-2}$ sequences.