IB Mathematics: Applications and Interpretation · Topic 3 · Geometry and trigonometry
3.16 Tree and cycle algorithms
Find minimum spanning trees with Kruskal’s and Prim’s algorithms, solve small Chinese postman problems, bound the travelling salesman problem, and choose a suitable algorithm for a routing task.
1/7A minimum spanning tree connects every vertex at least cost
- A minimum spanning tree connects every vertex at least cost
- Kruskal’s algorithm adds the cheapest edges that avoid cycles
- Prim’s algorithm grows one connected tree from a start vertex
- The Chinese postman problem finds the shortest route covering every edge
- A nearest neighbour cycle gives an upper bound on the salesman’s route
- Deleting a vertex gives a lower bound on the route
- The right algorithm depends on what the route must cover
- Check your recall
- Practice: 10 questions
Part 1 of 7: A minimum spanning tree connects every vertex at least cost
A council wants to link six villages by road. Every village must be reachable, with as little road as possible. A network of vertices and weighted edges models the problem. The weight of an edge is its length, cost or time.
A cycle is a closed path that returns to its start without repeating any other vertex. A spanning tree is a connected subgraph that reaches every vertex and has no cycle. With vertices, it always has exactly edges.
A minimum spanning tree is the spanning tree with the smallest total weight. Several different trees can share that minimum.
Key terms · tap one for its definition
cycle
A cycle is a closed path that begins and ends at the same vertex and repeats no other vertex or edge.
spanning tree
A spanning tree is a connected subgraph that contains every vertex of a graph and has no cycles.
minimum spanning tree
A minimum spanning tree is a spanning tree of a weighted graph whose total edge weight is as small as possible.
Part 2 of 7: Kruskal’s algorithm adds the cheapest edges that avoid cycles
Now a method is needed to find the cheapest tree. Kruskal’s algorithm builds it edge by edge, always taking the cheapest edge available. The steps are:
- Sort all edges from smallest weight to largest.
- Take the smallest edge not yet considered.
- Add it, unless it would complete a cycle.
- Stop when the tree has edges.
The tree may be several separate pieces at first. They join together as edges are added. Rejecting an edge is not an error. It means the two vertices are already connected.
Worked example
Kruskal’s algorithm on a road network
- Sort the edges: BC 2, AC 3, EF 4, AB 5, BD 6, CD 7, DE 8, CE 9, DF 10.
- Add BC 2, AC 3 and EF 4. None of them forms a cycle.
- Reject AB 5, because A and B are already joined through C.
- Add BD 6. Then reject CD 7, because C and D are now connected.
- Add DE 8. The tree has 5 edges, which equals , so stop.
Answer: The tree uses BC, AC, EF, BD and DE. Its total weight is .
Key term
Kruskal’s algorithm
Kruskal’s algorithm is a method that builds a minimum spanning tree by adding the lowest-weight edges that create no cycle.

Quick check
One question on the part you just read
Easy
Show answer and explanation
Answer: A · Worked explanation
Part 3 of 7: Prim’s algorithm grows one connected tree from a start vertex
Kruskal’s method can leave separate pieces along the way. Prim’s algorithm keeps a single tree throughout, starting from any vertex. The steps are:
- Choose a starting vertex.
- Find the cheapest edge joining the tree to a vertex outside it.
- Add that edge and its new vertex.
- Repeat until every vertex is in the tree.
Prim’s method needs no cycle check, because each new edge reaches a new vertex. On the same network, it must give a tree of the same total weight.
Worked example
Prim’s algorithm from vertex A
- From A, the cheapest edge is AC 3. The tree contains A and C.
- The cheapest edge leaving A and C is BC 2. Add B.
- From A, B and C, the choices are BD 6, CD 7 and CE 9. Add BD 6.
- From A, B, C and D, the cheapest edge is DE 8. Add E.
- The choices are now DF 10 and EF 4. Add EF 4 to reach F.
Answer: The edges are AC, BC, BD, DE and EF. The total is , which matches Kruskal’s result.
Key term
Prim’s algorithm
Prim’s algorithm is a method that grows a minimum spanning tree from one vertex by repeatedly adding the cheapest connecting edge.
Part 4 of 7: The Chinese postman problem finds the shortest route covering every edge
A postman must walk every street in a district and return to the depot. The aim is to walk as little as possible. This is the Chinese postman problem.
The degree of a vertex is the number of edges that meet there. If every degree is even, an Eulerian circuit exists. The postman then uses each edge once, so the route length equals the total weight.
If some vertices have odd degree, some edges must be walked twice. The number of odd vertices is always even. In that case:
- Identify the odd vertices.
- List every way of pairing them.
- Find the shortest path between the vertices in each pair.
- Choose the pairing with the smallest total, and add it to the total weight.
Worked example
A route that repeats one path
- The total weight of all roads is .
- The degrees are A 3, B 2, C 3 and D 2. The odd vertices are A and C.
- Only one pairing exists: A with C. The direct road is 8 km, but A to B to C is .
- The path via D is , so the shortest path is 7 km. Repeat it.
- The route length is .
Answer: The shortest route has length .
Key terms · tap one for its definition
Chinese postman problem
The Chinese postman problem is finding the minimum-weight closed route that uses every edge of a connected weighted graph at least once.
degree
The degree of a vertex is the number of edges that meet at that vertex.
Eulerian circuit
An Eulerian circuit is a closed route that starts and ends at the same vertex and uses every edge exactly once.

Quick check
One question on the part you just read
Easy
Show answer and explanation
Answer: B · Worked explanation
Part 5 of 7: A nearest neighbour cycle gives an upper bound on the salesman’s route
Sometimes a route must visit every vertex once rather than every edge. A salesman must visit every town once and return home. Finding the shortest such cycle is the travelling salesman problem. Assume every pair of towns is joined by an edge.
Any such cycle gives an upper bound, because the shortest cycle cannot be longer. The nearest neighbour algorithm builds one:
- Start at a chosen vertex.
- Move to the nearest unvisited vertex.
- Repeat until every vertex is visited.
- Return to the start and add the weights.
Key terms · tap one for its definition
travelling salesman problem
The travelling salesman problem is finding the minimum-weight cycle that visits every vertex exactly once and returns to the start.
upper bound
An upper bound is a value that the length of the shortest cycle cannot exceed, such as the length of any valid cycle.
Part 6 of 7: Deleting a vertex gives a lower bound on the route
An upper bound alone does not show how good a cycle is. A lower bound completes the picture. A lower bound is a value that the shortest cycle cannot go below. The deleted vertex algorithm finds one:
- Delete one vertex and all its edges.
- Find a minimum spanning tree of the remaining vertices.
- Add the two smallest edge weights at the deleted vertex.
Every cycle uses two edges at the deleted vertex. Its other edges connect all the remaining vertices, so they weigh at least as much as the tree. The shortest cycle therefore lies between the two bounds.
Worked example
Bounds for a four-town network
- From A, the nearest town is B (5). From B, the nearest unvisited town is C (4).
- From C, only D remains (9). Return from D to A (6).
- The cycle ABCDA has length . This is the upper bound.
- Delete A. The minimum spanning tree of B, C and D uses BC 4 and BD 7, with weight 11.
- The two smallest edges at A are AB 5 and AD 6, with weight 11. The lower bound is .
Answer: The shortest cycle lies between and .
Key term
lower bound
A lower bound is a value that the length of the shortest cycle cannot go below.
Part 7 of 7: The right algorithm depends on what the route must cover
Real problems rarely name the algorithm. The task itself shows which method fits. Compare what each task must cover.
Matching tasks to methods
- Task
- Link towns with cable
- Must cover
- Every vertex, no cycles
- Method
- Kruskal’s or Prim’s
- Task
- Grit every road, then return
- Must cover
- Every edge
- Method
- Chinese postman
- Task
- Visit every shop once, then return
- Must cover
- Every vertex once
- Method
- Nearest neighbour and deleted vertex
Check three things: what must be covered, whether the route returns to the start, and what the weights represent. Name the method and give the reason it fits. Real networks also have limits, such as one-way roads or time windows. State any assumption that simplifies the model, such as ignoring traffic. The result is a good starting plan, not always the final schedule.
Check your recall[15 marks]
6 written questions. Answer each one in your head or on paper, then open the mark scheme.
- 1.Define[2 marks]
Define a minimum spanning tree.
Show mark schemeHide mark scheme
Model answer
A minimum spanning tree is a connected subgraph of a weighted graph that contains every vertex, has no cycle, and has the smallest possible total weight.
- 1 mark for stating that it is a connected subgraph containing every vertex with no cycles
- 1 mark for stating that its total weight is the smallest possible
- 2.Calculate[3 marks]
Calculate the weight of a minimum spanning tree for a network with vertices P, Q, R and S and edges PQ 4, PR 2, QR 3, QS 5 and RS 6.
Show mark schemeHide mark scheme
Model answer
Sort the edges: PR 2, QR 3, PQ 4, QS 5, RS 6. Add PR 2 and QR 3. Reject PQ 4 because it forms a cycle. Add QS 5. The tree has 3 edges, so the weight is .
- 1 mark for adding PR 2 and QR 3 and rejecting PQ 4 because it forms a cycle
- 1 mark for adding QS 5 and stopping with edges
- 1 mark for obtaining a total weight of 10
- 3.Determine[3 marks]
Determine the length of the shortest route that uses every road and returns to its start, for roads AB 2 km, BC 3 km, CD 4 km, DA 7 km and BD 5 km.
Show mark schemeHide mark scheme
Model answer
The total weight is . Vertices B and D have odd degree. The shortest path between them is the direct road, 5 km. The route length is .
- 1 mark for finding the total weight of
- 1 mark for identifying B and D as the odd vertices and their shortest path as 5 km
- 1 mark for adding to obtain
- 4.Explain[2 marks]
Explain why the length of a nearest neighbour cycle gives only an upper bound for the travelling salesman problem.
Show mark schemeHide mark scheme
Model answer
The nearest neighbour cycle is one valid cycle, so the shortest cycle cannot be longer than it. A shorter valid cycle may exist, so its length need not be the minimum.
- 1 mark for stating that the shortest cycle cannot be longer than any valid cycle
- 1 mark for stating that a shorter cycle may exist, so this length may not be the minimum
- 5.Distinguish[2 marks]
Distinguish between the Chinese postman problem and the travelling salesman problem.
Show mark schemeHide mark scheme
Model answer
The Chinese postman problem asks for the shortest closed route that uses every edge at least once. The travelling salesman problem asks for the shortest cycle that visits every vertex exactly once.
- 1 mark for stating that the Chinese postman problem must cover every edge
- 1 mark for stating that the travelling salesman problem must visit every vertex once
- 6.Describe[3 marks]
Describe how to find a lower bound for the travelling salesman problem using the deleted vertex algorithm.
Show mark schemeHide mark scheme
Model answer
Delete one vertex and its edges. Find a minimum spanning tree of the remaining vertices. Add the two smallest edge weights at the deleted vertex to the weight of the tree.
- 1 mark for deleting a vertex and its edges
- 1 mark for finding a minimum spanning tree of the remaining vertices
- 1 mark for adding the two smallest edge weights at the deleted vertex

Practice this topic
10 quick-fire multiple-choice questions, easy to hard. Tap an answer to see if you're right and the worked explanation. (The written questions with mark schemes are under “Check your recall” above.)
0 right0 of 10 answered
Includes the 2 quick checks in the note above.
EasyIdentify[1 mark]
Show answer and explanation
Answer: C · Worked explanation
MediumCalculate[2 marks]
Show answer and explanation
Answer: A · Worked explanation
MediumIdentify[2 marks]
Show answer and explanation
Answer: D · Worked explanation
MediumDetermine[2 marks]
Show answer and explanation
Answer: B · Worked explanation
MediumCalculate[2 marks]
Show answer and explanation
Answer: C · Worked explanation
HardCalculate[2 marks]
Show answer and explanation
Answer: B · Worked explanation
HardDetermine[2 marks]
Show answer and explanation
Answer: D · Worked explanation
HardDeduce[2 marks]
Show answer and explanation
Answer: A · Worked explanation