Lesson 2: Finding minimum spanning trees

A graph with two minimum spanning trees

SkillFinding minimum spanning trees

Worked example

  • Complex familiar
  • Technology free

A graph has edges PQPQ 4, PRPR 3, QRQR 4, QSQS 5, RSRS 6 and STST 2. Find the weight of a minimum spanning tree, and decide whether the minimum spanning tree is unique.

1 of 5 steps
  1. Step 1: Order the edges

    STST 2, PRPR 3, PQPQ 4, QRQR 4, QSQS 5, RSRS 6.

Try a similar one

A fresh question of the same kind, checked as you answer, with hints and a full solution.

Method

  1. Run Kruskal's method as usual.

  2. At a tie, check whether choosing one of the equal edges rules out the other. If so, each choice gives a minimum spanning tree.

Watch out for

  • Choosing both PQPQ and QRQR, which forms a cycle.

  • Thinking that two different trees must have different weights.

Save your progress with a free account