Discrete Math · Undergraduate

Trees, Spanning Trees and Kruskal's Algorithm

Quick answer

A tree is a connected graph with no cycles. Trees have exactly n − 1 edges on n vertices, a unique path between any two vertices, and at least two leaves. A spanning tree of a connected graph keeps every vertex and only enough edges to stay connected. In a weighted graph, Kruskal's algorithm builds a minimum spanning tree by adding the cheapest remaining edge that does not close a cycle, the cheapest way to connect every site in a network.

What you'll learn

  • Recognize trees and forests
  • Use the n − 1 edge count and the degree sum for trees
  • Find a spanning tree of a connected graph
  • Find a minimum spanning tree with Kruskal's algorithm

Connected, with no cycles

A tree is a connected graph with no cycles. Family trees, folder structures and tournament brackets are trees. A forest is a graph with no cycles, connected or not: a collection of trees. A vertex of degree 11 is a leaf.

Trees on nn vertices share three facts:

  • they have exactly n−1n - 1 edges;
  • any two vertices are joined by exactly one path;
  • if n≥2n \ge 2, there are at least two leaves.

A spanning tree of a connected graph is a tree that uses all its vertices and some of its edges. When the edges carry costs, the cheapest one is a minimum spanning tree: the least cable, road or pipe that connects every site.

Why a tree has n − 1 edges

Grow the tree one leaf at a time. A single vertex has 00 edges. Every tree with at least 22 vertices has a leaf: follow a longest path; its last vertex has no edge back into the path (that would close a cycle) and none out of it (the path would be longer), so its degree is 11. Removing that leaf and its one edge leaves a smaller tree. Each leaf removed takes away one vertex and one edge, so vertices always outnumber edges by exactly one.

Kruskal’s algorithm

  1. Sort the edges from cheapest to most expensive.
  2. Take the cheapest edge that does not close a cycle with the edges already chosen.
  3. Repeat until n−1n - 1 edges are chosen.
A minimum spanning tree Five vertices A to E with seven weighted edges: A–B 4, A–C 3, B–C 2, B–D 5, C–D 7, C–E 6 and D–E 1. The four edges of the minimum spanning tree, D–E, B–C, A–C and B–D, are highlighted; the other three are dashed. The total weight is 11. 1 2 3 4 5 6 7 A B C D E
A minimum spanning tree

Worked examples

Common mistakes

Practice problems

  1. A tree has 1212 vertices. How many edges does it have?

    Answer

    1111

    Full solution

    A tree on nn vertices has n−1n - 1 edges.

  2. A connected graph has 1010 vertices and 99 edges. Is it a tree?

    Answer

    Yes

    Full solution

    Connected with n−1n - 1 edges forces no cycles: a spanning tree inside it already has all 99 edges.

  3. A forest has 2020 vertices and 33 trees. How many edges does it have?

    Answer

    1717

    Full solution

    Each tree has one fewer edge than vertices, so the forest has 20−320 - 3.

  4. How many spanning trees does a cycle with 99 vertices have?

    Answer

    99

    Full solution

    Remove any one of the 99 edges.

  5. How many trees are there on 55 labeled vertices?

    Answer

    125125

    Full solution

    Cayley’s formula: 55−2=1255^{5-2} = 125.

  6. In the figure, edge B–D costs 99 instead of 55. What is the weight of the minimum spanning tree now?

    Answer

    1212

    Full solution

    Take 11, 22 and 33 as before, skip 44, and take C–E (66) to reach D and E: 1+2+3+61 + 2 + 3 + 6.

  7. A tree has 33 vertices of degree 44, 22 of degree 22, and the rest are leaves. How many leaves?

    Answer

    88

    Full solution

    With LL leaves, n=5+Ln = 5 + L and the degree sum 12+4+L12 + 4 + L equals 2(n−1)=8+2L2(n - 1) = 8 + 2L, so L=8L = 8.

  8. A student running Kruskal in the figure takes A–B (44) after A–C and B–C. What is wrong?

    Answer

    A–B closes the cycle A–B–C and must be skipped.

    Full solution

    A and B are already joined through C, so A–B adds cost without connecting anything new.

Frequently asked questions

What is a tree in graph theory?

A connected graph with no cycles. Equivalently, a graph in which every two vertices are joined by exactly one path.

How many edges does a tree have?

Exactly n − 1 on n vertices. A connected graph with n vertices and n − 1 edges is always a tree.

What is a spanning tree?

A tree inside a connected graph that uses every vertex. It is found by deleting edges from cycles until none remain.

How does Kruskal's algorithm work?

Sort the edges by weight. Add them one at a time, cheapest first, skipping any edge that would close a cycle, until n − 1 edges are chosen.

How many trees are there on n labeled vertices?

nⁿ⁻², Cayley's formula. On 4 labeled vertices there are 16, which is also the number of spanning trees of the complete graph K₄.

What to learn next