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 is a leaf.
Trees on vertices share three facts:
- they have exactly edges;
- any two vertices are joined by exactly one path;
- if , 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 edges. Every tree with at least 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 . 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
- Sort the edges from cheapest to most expensive.
- Take the cheapest edge that does not close a cycle with the edges already chosen.
- Repeat until edges are chosen.
Worked examples
Common mistakes
Practice problems
-
A tree has vertices. How many edges does it have?
Answer
Full solution
A tree on vertices has edges.
-
A connected graph has vertices and edges. Is it a tree?
Answer
Yes
Full solution
Connected with edges forces no cycles: a spanning tree inside it already has all edges.
-
A forest has vertices and trees. How many edges does it have?
Answer
Full solution
Each tree has one fewer edge than vertices, so the forest has .
-
How many spanning trees does a cycle with vertices have?
Answer
Full solution
Remove any one of the edges.
-
How many trees are there on labeled vertices?
Answer
Full solution
Cayley’s formula: .
-
In the figure, edge B–D costs instead of . What is the weight of the minimum spanning tree now?
Answer
Full solution
Take , and as before, skip , and take C–E () to reach D and E: .
-
A tree has vertices of degree , of degree , and the rest are leaves. How many leaves?
Answer
Full solution
With leaves, and the degree sum equals , so .
-
A student running Kruskal in the figure takes A–B () 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₄.