Scribe logoScribeNotes & practice
Sign inStart free
  1. Notes
  2. ›IB Mathematics: Applications and Interpretation
  3. ›3 Geometry and trigonometry
  4. ›3.16 Tree and cycle algorithms

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.

  • 8 min read
  • 7 parts
  • 10 questions
  • Draft
  • HL only
Start a Quick 5 on this topic→Jump to the 10 questions
1/7A minimum spanning tree connects every vertex at least cost
  1. 1A minimum spanning tree connects every vertex at least cost
  2. 2Kruskal’s algorithm adds the cheapest edges that avoid cycles
  3. 3Prim’s algorithm grows one connected tree from a start vertex
  4. 4The Chinese postman problem finds the shortest route covering every edge
  5. 5A nearest neighbour cycle gives an upper bound on the salesman’s route
  6. 6Deleting a vertex gives a lower bound on the route
  7. 7The right algorithm depends on what the route must cover
  8. Check your recall
  9. Practice: 10 questions
1

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 nnn vertices, it always has exactly n−1n-1n−1 edges.

A minimum spanning tree is the spanning tree with the smallest total weight. Several different trees can share that minimum.

Common mistake

A minimum spanning tree is not the shortest route between two vertices. It is the cheapest way to connect all of them.

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 1 done

2

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 n−1n-1n−1 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

A network has vertices A to F. The edge weights, in km, are AB 5, AC 3, BC 2, BD 6, CD 7, CE 9, DE 8, DF 10 and EF 4. Find a minimum spanning tree and its total weight.
  1. 1
    Sort the edges: BC 2, AC 3, EF 4, AB 5, BD 6, CD 7, DE 8, CE 9, DF 10.
  2. 2
    Add BC 2, AC 3 and EF 4. None of them forms a cycle.
  3. 3
    Reject AB 5, because A and B are already joined through C.
  4. 4
    Add BD 6. Then reject CD 7, because C and D are now connected.
  5. 5
    Add DE 8. The tree has 5 edges, which equals 6−16-16−1, so stop.

Answer: The tree uses BC, AC, EF, BD and DE. Its total weight is 2+3+4+6+8=23 km2+3+4+6+8=23\,\mathrm{km}2+3+4+6+8=23km.

Figure 1. The thick edges form a tree that connects all six vertices with total weight 23.

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.

Part 2 done

Quick check

One question on the part you just read

Easy

A connected network has 8 vertices. Identify the number of edges in any spanning tree of it.
Show answer and explanation

Answer: A · Worked explanation

A spanning tree on nnn vertices has n−1n-1n−1 edges, so 8 vertices give 7 edges. A count of 8 would leave one edge too many, and that extra edge would complete a cycle. Counting edges this way gives a quick check that a proposed tree misses no vertex and contains no cycle.
3

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

Use Prim’s algorithm, starting at A, on the same network with weights in km.
  1. 1
    From A, the cheapest edge is AC 3. The tree contains A and C.
  2. 2
    The cheapest edge leaving A and C is BC 2. Add B.
  3. 3
    From A, B and C, the choices are BD 6, CD 7 and CE 9. Add BD 6.
  4. 4
    From A, B, C and D, the cheapest edge is DE 8. Add E.
  5. 5
    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 3+2+6+8+4=23 km3+2+6+8+4=23\,\mathrm{km}3+2+6+8+4=23km, which matches Kruskal’s result.

Exam tip

List the edges in the order you add them, then state the total weight. Check that the tree has n−1n-1n−1 edges.

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 3 done

4

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

A network has roads AB 3 km, BC 4 km, CD 5 km, DA 6 km and AC 8 km. Find the length of the shortest route that uses every road and returns to its start.
  1. 1
    The total weight of all roads is 3+4+5+6+8=26 km3+4+5+6+8=26\,\mathrm{km}3+4+5+6+8=26km.
  2. 2
    The degrees are A 3, B 2, C 3 and D 2. The odd vertices are A and C.
  3. 3
    Only one pairing exists: A with C. The direct road is 8 km, but A to B to C is 3+4=7 km3+4=7\,\mathrm{km}3+4=7km.
  4. 4
    The path via D is 6+5=11 km6+5=11\,\mathrm{km}6+5=11km, so the shortest path is 7 km. Repeat it.
  5. 5
    The route length is 26+7=33 km26+7=33\,\mathrm{km}26+7=33km.

Answer: The shortest route has length 33 km33\,\mathrm{km}33km.

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.

Part 4 done

Quick check

One question on the part you just read

Easy

Identify the condition that guarantees an Eulerian circuit in a connected network.
Show answer and explanation

Answer: B · Worked explanation

A closed route using each edge once needs every vertex entered and left equally often, so all degrees are even. Exactly two odd vertices would force a route that starts and ends at different vertices, so it is not a circuit.
5

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.

Common mistake

The nearest neighbour cycle is not always the shortest cycle. A better cycle may exist, so its length is only an upper bound.

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 5 done

6

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

Four towns A, B, C and D are joined in pairs. The distances in km are AB 5, AC 8, AD 6, BC 4, BD 7 and CD 9. Find an upper bound by nearest neighbour from A, and a lower bound by deleting A.
  1. 1
    From A, the nearest town is B (5). From B, the nearest unvisited town is C (4).
  2. 2
    From C, only D remains (9). Return from D to A (6).
  3. 3
    The cycle ABCDA has length 5+4+9+6=24 km5+4+9+6=24\,\mathrm{km}5+4+9+6=24km. This is the upper bound.
  4. 4
    Delete A. The minimum spanning tree of B, C and D uses BC 4 and BD 7, with weight 11.
  5. 5
    The two smallest edges at A are AB 5 and AD 6, with weight 11. The lower bound is 11+11=22 km11+11=22\,\mathrm{km}11+11=22km.

Answer: The shortest cycle lies between 22 km22\,\mathrm{km}22km and 24 km24\,\mathrm{km}24km.

Key term

lower bound

A lower bound is a value that the length of the shortest cycle cannot go below.

Part 6 done

7

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

TaskMust coverMethod
Link towns with cableEvery vertex, no cyclesKruskal’s or Prim’s
Grit every road, then returnEvery edgeChinese postman
Visit every shop once, then returnEvery vertex onceNearest neighbour and deleted vertex
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.

Note read

Check your recall[15 marks]

6 written questions. Answer each one in your head or on paper, then open the mark scheme.

  1. 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. 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 2+3+5=102+3+5=102+3+5=10.

    • 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 4−1=34-1=34−1=3 edges
    • 1 mark for obtaining a total weight of 10
  3. 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 2+3+4+7+5=21 km2+3+4+7+5=21\,\mathrm{km}2+3+4+7+5=21km. Vertices B and D have odd degree. The shortest path between them is the direct road, 5 km. The route length is 21+5=26 km21+5=26\,\mathrm{km}21+5=26km.

    • 1 mark for finding the total weight of 21 km21\,\mathrm{km}21km
    • 1 mark for identifying B and D as the odd vertices and their shortest path as 5 km
    • 1 mark for adding to obtain 26 km26\,\mathrm{km}26km
  4. 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. 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. 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.

3.

Easy·Identify[1 mark]

Identify the task that is best modelled by a minimum spanning tree.
Show answer and explanation

Answer: C · Worked explanation

A minimum spanning tree connects every vertex with the least total weight and needs no return. Treating every road is a Chinese postman task, and visiting shops once is a travelling salesman task. Check the requirement first: every vertex linked, no return needed, and no need to cover every road.
4.

Medium·Calculate[2 marks]

A network has vertices P, Q, R and S with edges PQ 6, PR 4, QR 5, QS 3 and RS 8. Calculate the weight of a minimum spanning tree.
Show answer and explanation

Answer: A · Worked explanation

Sort the edges: QS 3, PR 4, QR 5, PQ 6, RS 8. Add QS, PR and QR, which gives 3 edges for 4 vertices, so the weight is 3+4+5=123+4+5=123+4+5=12. A total of 18 adds PQ 6 as well, which would form a cycle.
5.

Medium·Identify[2 marks]

Prim’s algorithm starts at A on a network with edges AB 7, AC 4, BC 5, BD 2 and CD 6. Identify the second edge added to the tree.
Show answer and explanation

Answer: D · Worked explanation

The first edge is AC 4, the cheapest at A. The edges leaving A and C are AB 7, BC 5 and CD 6, so BC 5 is next. BD 2 is the cheapest edge overall, but it does not yet touch the tree.
6.

Medium·Determine[2 marks]

A network has roads PQ 5 km, QR 6 km, RP 7 km and RS 4 km. Determine the length of the shortest route that uses every road and returns to its start.
Show answer and explanation

Answer: B · Worked explanation

The total weight is 5+6+7+4=22 km5+6+7+4=22\,\mathrm{km}5+6+7+4=22km. Vertices R and S have odd degree, and their shortest path is 4 km, so the route is 22+4=26 km22+4=26\,\mathrm{km}22+4=26km. A length of 22 km leaves out the repeated road, and 29 km repeats the longest road instead.
7.

Medium·Calculate[2 marks]

Four towns have distances AB 12, AC 9, AD 16, BC 14, BD 11 and CD 8, all in km. Calculate the cycle length given by nearest neighbour from A.
Show answer and explanation

Answer: C · Worked explanation

From A, the nearest town is C (9). From C, the nearest unvisited town is D (8), then B (11), then back to A (12). The total is 9+8+11+12=40 km9+8+11+12=40\,\mathrm{km}9+8+11+12=40km. A value of 28 km leaves out the return edge, and 70 km adds every edge.
8.

Hard·Calculate[2 marks]

Four towns have distances AB 7, AC 10, AD 5, BC 6, BD 9 and CD 12. Calculate the lower bound found by deleting D with the deleted vertex algorithm.
Show answer and explanation

Answer: B · Worked explanation

The minimum spanning tree of A, B and C uses BC 6 and AB 7, with weight 13. The two smallest edges at D are DA 5 and DB 9, with weight 14. The lower bound is 13+14=2713+14=2713+14=27. A value of 13 forgets the edges at D.
9.

Hard·Determine[2 marks]

A network has roads AB 4, AC 6, AD 5, BC 3, BD 7 and CD 2, in km. Every vertex has odd degree. Determine the length of the shortest route that uses every road and returns to its start.
Show answer and explanation

Answer: D · Worked explanation

The total weight is 27 km27\,\mathrm{km}27km. The pairing AB with CD costs 4+2=64+2=64+2=6. Pairing AD with BC costs 5+3=85+3=85+3=8, and AC with BD costs 6+5=116+5=116+5=11 using the path B to C to D. The least is 6, so the route is 27+6=33 km27+6=33\,\mathrm{km}27+6=33km. The value 35 comes from pairing AD with BC.
10.

Hard·Deduce[2 marks]

A lower bound for a salesman’s route is 62 km. A nearest neighbour cycle gives an upper bound of 68 km. Deduce which statement must be true.
Show answer and explanation

Answer: A · Worked explanation

The shortest cycle cannot be below the lower bound or above the upper bound, so it lies between 62 km and 68 km. The upper bound is only one cycle’s length, so other cycles can be longer, and it need not be the shortest.

Keep going

Next topic4.1 Sampling conceptsPrevious topic3.15 Adjacency matrices

More in Topic 3 · Geometry and trigonometry

  1. 3.8Unit circle and identitiesNotes · 10 questions· HL only
  2. 3.9Matrix transformationsNotes · 10 questions· HL only
  3. 3.10Vector conceptsNotes · 10 questions· HL only
  4. 3.11Vector equation of a lineNotes · 10 questions· HL only
  5. 3.12Vectors in kinematicsNotes · 10 questions· HL only
  6. 3.13Scalar and vector productsNotes · 10 questions· HL only
  7. 3.14Graph theoryNotes · 10 questions· HL only
  8. 3.15Adjacency matricesNotes · 10 questions· HL only
  9. 3.16Tree and cycle algorithmsNotes · 10 questions· HL only

All IB Mathematics: Applications and Interpretation topics →

Draft: written by Scribe and checked automatically, not yet by a subject reviewer.

Practice questions are original, written by Scribe and checked automatically for correctness.

Topic codes follow the official numbering. Not endorsed by IB Diploma Programme or any exam board.

On this page

0/7 read

  1. 1A minimum spanning tree connects every vertex at least cost
  2. 2Kruskal’s algorithm adds the cheapest edges that avoid cycles
  3. 3Prim’s algorithm grows one connected tree from a start vertex
  4. 4The Chinese postman problem finds the shortest route covering every edge
  5. 5A nearest neighbour cycle gives an upper bound on the salesman’s route
  6. 6Deleting a vertex gives a lower bound on the route
  7. 7The right algorithm depends on what the route must cover
  8. Check your recall
  9. Practice: 10 questions
All coursesScribeHow it worksPricingPrivacyTerms

Notes and questions are written by Scribe in our own words. Topic codes follow the official course numbering so you can find your place. Not produced or endorsed by the IB, College Board, AQA, OCR, Pearson Edexcel or any exam board.

© 2026 Scribe