Trees and Spanning Trees

A tree is simply a graph that connects everything with no loops, so there's exactly one way to get between any two points. The name comes from the picture: draw one from a single starting point and it branches out like a real tree, with no branches growing back together. Trees are good for building the cheapest network that still reaches everyone, and for organizing things in levels, like folders on a computer. The formulas are two short facts: $|E| = |V| - 1$ (a tree always has one fewer edge than it has vertices) and $n^{n-2}$ (how many different trees you can draw on $n$ labeled vertices). Nothing scary, just two numbers to know.

Why exactly $n - 1$ edges? Build the tree one edge at a time. Start with $n$ separate vertices, so $n$ pieces. Every edge you add without making a loop joins two separate pieces into one, so the number of pieces drops by exactly 1. You're done when there's one piece, and that takes $n - 1$ edges.

That's why there are several equivalent definitions of a tree on $n$ vertices: connected with no cycles; connected with $n - 1$ edges; no cycles with $n - 1$ edges; exactly one path between any two vertices. A tree sits right on the edge. Remove any edge and it falls apart into two pieces; add any edge and it gains exactly one cycle, made of the new edge and the one path that already joined its ends.

Rooted trees pick one vertex as the top, and then every other vertex has a parent, the next vertex up toward the root. In a binary tree each vertex has at most two children, so each level can be twice as big as the one above, and depth $d$ allows up to $2^d$ leaves. Turned around, that means you can reach any of $2^d$ leaves in only $d$ steps, which is why binary search trees and tournament brackets are so efficient.

Spanning trees. A spanning tree of a connected graph uses all its vertices and some of its edges, just enough to stay connected. You can always find one: as long as there's a cycle, remove one of its edges, which can't disconnect anything. Cayley's formula counts the spanning trees of $K_n$: $n^{n-2}$.

Minimum spanning trees. Now give each edge a cost and ask for the cheapest spanning tree. Kruskal's algorithm sorts the edges by weight and adds each one unless it would create a cycle. Prim's algorithm grows a single tree from one vertex, always adding the cheapest edge leaving it. Both are greedy, meaning they grab the best-looking option at each step and never take it back. Greedy methods usually aren't guaranteed to win, but for spanning trees both always give a minimum one.

A common mistake. It's tempting to treat Kruskal like Prim and only add edges that touch what you've built so far. Kruskal doesn't care about that. It can build several separate little trees at once, as long as no edge closes a cycle, and they merge into one tree by the end.

Network designers connect sites with the least cable using minimum spanning trees, and file systems, decision trees and family trees are all rooted trees.