Minimum spanning trees: Kruskal's algorithm

Kruskal's algorithm

1. List the edges in order of weight, smallest first.

2. Take the smallest unused edge. Add it to the tree unless it makes a cycle, in which case reject it.

3. Repeat until n - 1 edges have been accepted (for n vertices).

Show your working

Write the edges in the order you consider them and mark each as accepted or rejected, for example 'EF 3 accept, DE 4 accept, ..., AB 7 reject (makes a cycle ABC)'. Writing just the final tree loses marks. Equal weights may be taken in either order; the total weight is the same.

Kruskal versus Prim

Kruskal looks at the whole network and the tree can be in separate pieces until the end. It is awkward with a distance matrix, because you have to sort every entry. Prim (next lesson) grows a single tree.

Worked example

Use Kruskal's algorithm on network N (see table) to find a minimum spanning tree.

1. EF (3): accept
2. DE (4): accept
3. AC (5): accept
4. BC (6): accept
5. AB (7): reject, makes a cycle
6. CD (8): accept
7. FG (8): accept
8. 6 edges for 7 vertices: stop

Answer: Tree EF, DE, AC, BC, CD, FG, total weight 34

Check yourself

1. Find the total weight of the minimum spanning tree of network N.
   Show answer

   34. Accepted edges: EF (3), DE (4), AC (5), BC (6), CD (8), FG (8). Total 34.

2. When Kruskal's algorithm is used on network N, which is the first edge to be rejected?
   • AC
   • AB
   • CD
   • FG
   Show answer

   AB. After EF, DE, AC and BC are accepted, AB (7) would make the cycle ABCA, so it is rejected.

3. A network has 15 vertices. How many edges are accepted by Kruskal's algorithm?
   Show answer

   14. A spanning tree on n vertices has n - 1 = 14 edges.

4. In Kruskal's algorithm on network N, which edge is accepted last?
   • FG
   • DF
   • BE
   • AD
   Show answer

   FG. The accepted edges in order are EF, DE, AC, BC, CD, FG. FG brings in G, completing the tree.

5. In Kruskal's algorithm, when is an edge rejected?
   • When it is longer than the previous edge
   • When it is not joined to the tree so far
   • When adding it would create a cycle
   • When it touches a vertex already used
   Show answer

   When adding it would create a cycle. The only reason to reject is a cycle. Kruskal's tree may be disconnected part-way through.

6. Why is Kruskal's algorithm less suitable than Prim's for a large distance matrix?
   • All the edges must first be sorted by weight
   • It can only be used on graphs with even degrees
   • It does not always give a minimum spanning tree
   • It cannot reject edges
   Show answer

   All the edges must first be sorted by weight. Kruskal needs the edges in order, which for a matrix means sorting many entries, and checking for cycles is hard to see in a table.

Practise with instant feedback Print this lesson

Sources

• Pearson Edexcel International Advanced Level in Mathematics specification (issue 3)
• Pearson Edexcel IAL Decision Mathematics 1 scheme of work

Last updated 7 November 2026. Spotted a mistake? Tell us.