Skip to content
Tutorials Center
My learning

Topics

Lesson 46 of 68 ยท Graph Theory

Trees and Spanning Trees

Learn tree properties, Cayley's formula and spanning trees, then build minimum spanning trees with Kruskal and Prim and encode trees as Prufer codes.

A tree is a connected graph with no cycles. It is the leanest way to keep a set of vertices connected: remove any edge and something falls off, add any edge and a cycle appears. File systems, family trees, HTML documents, decision diagrams and the routing tables of networks are all trees, and many graph algorithms work by finding a tree hidden inside a bigger graph.

In this lesson we pin down what makes a graph a tree, learn the vocabulary of rooted trees, count labeled trees with Cayley's formula and extract cheap spanning trees from weighted graphs with Kruskal's and Prim's algorithms. We finish with Prufer codes, a lovely way to turn a tree into a short sequence of numbers. The data-structure side is covered in Minimum Spanning Tree and Union-Find; here the emphasis is on why the facts are true.

Tree facts that all say the same thing

Connected, no cycles The definition.
n - 1 edges Exactly one fewer edge than vertices.
Unique paths One path between any two vertices.
Every edge is a bridge Cut one and it splits in two.
1 / 2

What makes a graph a tree

For a graph T with n vertices, the following statements are all equivalent, so any one can serve as the definition:

  1. T is connected and has no cycles.
  2. T is connected and has exactly n - 1 edges.
  3. T has no cycles and exactly n - 1 edges.
  4. There is exactly one path between every pair of vertices.
  5. T is connected, and removing any edge disconnects it.

Why n - 1? Start with n isolated vertices (n components). Each added edge in a tree joins two different components, because an edge inside a component would close a cycle. Each such edge lowers the component count by one, and we need to go from n components to 1, so exactly n - 1 edges are used.

Every tree with at least two vertices has at least two leaves (vertices of degree 1): follow a longest path, and both of its ends must be leaves. A graph made of several trees is a forest.

Rooted trees

Pick one vertex as the root and orient everything away from it. Now the familiar family vocabulary applies: every non-root vertex has one parent (the neighbor on the path toward the root), its other neighbors are children, vertices with no children are leaves, and the depth of a vertex is its distance from the root. The height of the tree is its greatest depth. A rooted tree where each vertex has at most two children is a binary tree; the binary trees in the DSA track are rooted trees in exactly this sense.

Python Is it a tree? Leaves, depth and Cayley's formula

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Cayley's formula says there are exactly n^(n-2) labeled trees on n vertices, i.e., spanning trees of the complete graph K_n. The brute-force run above confirms it for n up to 6 (1, 3, 16, 125, 1296). The Prufer codes at the end of this lesson show why it is true.

Spanning trees and minimum spanning trees

A spanning tree of a connected graph G is a subgraph that contains all vertices of G and is a tree. Every connected graph has one: while a cycle remains, delete one of its edges (the graph stays connected); when no cycles are left, you have a tree. A graph with n vertices and m edges therefore needs m - (n - 1) deletions.

If edges carry weights (cable cost, distance), a minimum spanning tree (MST) is a spanning tree of least total weight. The classic task: connect several offices with the cheapest set of cables. Two greedy algorithms both find an MST.

Kruskal's algorithm sorts edges by weight and adds each edge unless it would close a cycle. To test for cycles quickly, keep the components in a union-find structure: an edge is allowed exactly when its endpoints are in different components.

Prim's algorithm grows a single tree. Start at any vertex, and repeatedly add the cheapest edge leaving the current tree, using a priority queue.

Both work because of the cut property: for any split of the vertices into two groups, the cheapest edge crossing the split belongs to some MST. Each greedy step picks such an edge. When edge weights are all different, the MST is unique, and both algorithms must return the same tree.

Python Kruskal and Prim find the same minimum spanning tree

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The total weight is 39 for both. Notice that the two algorithms add edges in a different order; only the final set is the same here. When several edges share a weight, different tie-breaking can give different MSTs of equal total weight.

Prufer codes

How many labeled trees are there on vertices 0, 1, ..., n-1? Heinz Prufer gave a bijection between trees and sequences of length n - 2 over those labels. The encoding is simple: repeat n - 2 times, find the smallest-numbered leaf, write down its neighbor, and delete the leaf. The decoding rebuilds the tree: a vertex appears in the code exactly degree - 1 times, so you can recover all degrees and then reconnect the smallest available leaf to each code entry in turn. Finally join the two vertices that remain.

Since every sequence of length n - 2 over n labels decodes to exactly one tree, the number of trees equals the number of sequences, n^(n-2). That is a proof of Cayley's formula.

Python Encode a tree to a Prufer code and decode it back

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The centre of a star has degree 4, so it appears 3 times: the code is [0, 0, 0]. Leaves never appear in the code at all, since a leaf has degree 1 and 1 - 1 = 0.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. A connected graph has 12 vertices and 11 edges. What is it?

    A connected graph on n vertices with n - 1 edges is a tree.
  2. 2. How many labeled trees exist on 5 vertices?

    Cayley's formula gives n^(n-2) = 5^3 = 125.
  3. 3. How many edges must be removed from a connected graph with 9 vertices and 15 edges to get a spanning tree?

    A spanning tree has 9 - 1 = 8 edges, so 15 - 8 = 7 edges must go.
  4. 4. In Kruskal's algorithm, when is an edge rejected?

    Kruskal considers edges in increasing weight order and skips any edge whose endpoints are already connected.
  5. 5. A tree has Prufer code [3, 3, 1, 3] on 6 vertices. How many times does vertex 3 appear, and what is its degree?

    Vertex 3 appears three times in the code, and a vertex appears degree - 1 times, so its degree is 4.

Summary

  • A tree is a connected acyclic graph; equivalently a connected graph with n - 1 edges, or a graph with a unique path between every pair of vertices.
  • Every tree with at least two vertices has at least two leaves; rooting a tree gives parents, children, depth and height.
  • Cayley's formula: there are n^(n-2) labeled trees on n vertices, which Prufer codes prove with a bijection.
  • Every connected graph has a spanning tree; with weights, Kruskal (sort edges, skip cycles) and Prim (grow from a vertex) both build a minimum spanning tree.
  • The cut property is why the greedy choice is safe.

Next: Graph Coloring and Planarity, where we label vertices so neighbors differ.