Ceist Eile

Ceist Eile is in development. Features, questions and prices may change while we refine it.

Subjects · Leaving Cert Applied Maths

Leaving Cert Applied Maths: Minimum spanning trees

How often Minimum spanning trees comes up on the Applied Maths papers, every year it was asked, and questions to try.

HL Asked on 3 of the last 3 Higher Level papers, most recently in 2025. banker

OL Asked on 3 of the last 3 Ordinary Level papers, most recently in 2025. banker

Minimum spanning trees, Higher Level(6 marks)

Quick ones on Minimum spanning trees.

(a)What is a spanning tree of a connected network?
  1. A cycle that passes through every vertex
  2. A tree that includes every vertex
  3. The shortest path between two vertices
(b)What is the first step of Kruskal's algorithm?
  1. Give the start vertex a label of 0
  2. Pick any vertex as the start of the tree
  3. List all edges in increasing order of weight
(c)Kruskal's algorithm: when is the next-cheapest edge rejected?
  1. When it would complete a cycle
  2. When its weight equals an earlier edge
  3. When it touches a vertex already chosen
Show the answers

(a) A tree that includes every vertex

(b) List all edges in increasing order of weight

(c) When it would complete a cycle

Your turn: Higher Level questions on Minimum spanning trees.

Higher Level

Asked on 3 of the last 3 Higher Level papers, most recently in 2025. banker

Every paper, year by year

YearWhere it came up
2025Q3
2024Q1
2023Q7

Links open the State Examinations Commission’s paper for that year.

More Minimum spanning trees questions

Minimum spanning trees, 3 marks

A connected network has all edge weights different. How many minimum spanning trees does it have?

  1. Always at least two
  2. It depends on the start vertex
  3. Exactly one
Show the answer

Exactly one

With distinct weights there are never ties to break, so Kruskal and Prim (from any start) always build the same tree. Two different MSTs can only exist when some weights are equal.

Minimum spanning trees, 3 marks

Prim's algorithm on a distance table: after choosing the start, where do you look for the next edge?

  1. Only in the start vertex's column, every time
  2. In the columns of vertices already in the tree
  3. Anywhere in the whole table, for the smallest entry
Show the answer

In the columns of vertices already in the tree

Each step picks the cheapest link from the tree built so far to a new vertex. So only the columns of vertices already chosen are searched, with rows of chosen vertices crossed out.

Minimum spanning trees, 3 marks

Kruskal's on edges PQ 3, PR 4, QR 2, QS 6, RS 5, ST 1. Which edge is rejected first?

  1. PR
  2. QS
  3. RS
Show the answer

PR

In order: ST 1 in, QR 2 in, PQ 3 in. PR 4 would join P and R, which are already linked through Q, so it would make a cycle and is rejected. RS 5 is then accepted.

Ordinary Level

Asked on 3 of the last 3 Ordinary Level papers, most recently in 2025. banker

Every paper, year by year

YearWhere it came up
2025Q4, Q9
2024Q6
2023Q4

Links open the State Examinations Commission’s paper for that year.

More Minimum spanning trees questions

Minimum spanning trees, 2 marks

What is a minimum spanning tree?

  1. The shortest path between two vertices
  2. A tree with the fewest vertices
  3. A spanning tree with the smallest total weight
Show the answer

A spanning tree with the smallest total weight

Of all the trees that connect every vertex, the MST has the least total weight, e.g. the least cable needed to link every house.

Minimum spanning trees, 3 marks

At each step of Prim's algorithm you add…

  1. The edge that forms a cycle
  2. The cheapest edge joining the tree to a new vertex
  3. The cheapest edge anywhere in the network
Show the answer

The cheapest edge joining the tree to a new vertex

Prim grows one tree from a start vertex. Each step looks only at edges from the tree to vertices not yet in it and picks the lightest.

Minimum spanning trees, 3 marks

A network has 8 vertices. How many edges are in any spanning tree?

  1. 7
  2. 8
  3. 9
Show the answer

7

A tree on n vertices always has n − 1 edges. With 8 vertices that is 7 edges: one more would make a cycle, one fewer would leave a vertex out.

Other Applied Maths topics

All of Leaving Cert Applied Maths