Open Math›Year 11›Mathematics Standard›Networks, paths and trees›Shortest paths and spanning trees

Shortest paths and spanning trees

Identify trees and spanning trees in a network; find the minimum spanning tree and the shortest path between two vertices and explain why these may differ.

Worked examples

Identifying trees and counting edges in a spanning tree

Straightforward

Problem

A connected network has

6

vertices. (a) How many edges must a spanning tree of this network have? (b) A connected subgraph of this network has

6

vertices and

6

edges. Is this subgraph a spanning tree? Give a reason.

Apply the formula for the number of edges in a spanning tree.

A spanning tree on

n

vertices has exactly

n - 1

edges. Here

n = 6

, so a spanning tree has

6 - 1 = 5

edges.

Compare the number of edges in the subgraph with the number required for a spanning tree.

The subgraph has

6

edges but a spanning tree on

6

vertices must have exactly

5

edges. The subgraph has one edge too many.

State the conclusion using the definition of a tree.

A tree is connected and contains no cycles. Having

6

edges on

6

vertices means the subgraph contains at least one cycle, so it is not a spanning tree.

Answer

(a) A spanning tree of this network has

5

edges. (b) No — the subgraph has

6

edges, but a spanning tree on

6

vertices must have exactly

5

; the extra edge creates a cycle.

Finding the minimum spanning tree using Kruskal's algorithm

Moderate

Problem

A network has vertices

A

B

C

D

E

with edges

AB

(weight

4

AC

(weight

2

BC

(weight

1

BD

(weight

5

CD

(weight

3

) and

CE

(weight

4

). Find the minimum spanning tree and state its total weight.

List all edges in ascending order of weight.

BC

(1),

AC

(2),

CD

(3),

AB

(4),

CE

(4),

BD

(5)

Add the smallest edge. It connects two separate vertices, so no cycle is formed.

Add

BC

(weight

1

). Connected components:

B

–

C

and the isolated vertices

A

D

E

Continue adding edges in order, skipping any that would create a cycle.

Add

AC

(weight

2

): connects

A

to the

B

–

C

component. Components:

A

–

B

–

C

D

E

.
Add

CD

(weight

3

): connects

D

. Components:

A

–

B

–

C

–

D

E

.
Skip

AB

(weight

4

): both

A

and

B

are already in the same component — adding this edge would create a cycle.
Add

CE

(weight

4

): connects

E

. All

5

vertices are now connected — stop.

Calculate the total weight of the minimum spanning tree.

MST edges:

BC

(1),

AC

(2),

CD

(3),

CE

(4).

\text{Total weight} = 1 + 2 + 3 + 4 = 10

Answer

The minimum spanning tree uses edges

BC

AC

CD

and

CE

with total weight

10

Finding the minimum spanning tree and shortest path

Challenging

Problem

A network has vertices

A

B

C

D

E

with edges

AB

(weight

2

AC

(weight

6

BC

(weight

3

BD

(weight

8

CD

(weight

4

CE

(weight

7

) and

DE

(weight

5

). (a) Find the minimum spanning tree and state its total weight. (b) Find the shortest path from

A

E

and state its length. (c) Explain in one sentence why the path from

A

E

through the MST may differ from the shortest path.

Sort all edges by weight to prepare for Kruskal's algorithm.

AB

(2),

BC

(3),

CD

(4),

DE

(5),

AC

(6),

CE

(7),

BD

(8)

Build the MST by adding edges one at a time, skipping any that create a cycle.

Add

AB

(2): connects

A

and

B

.
Add

BC

(3): connects

C

to the

A

–

B

component.
Add

CD

(4): connects

D

.
Add

DE

(5): connects

E

. All

5

vertices are now connected — stop.
MST edges:

AB

BC

CD

DE

\text{MST total weight} = 2 + 3 + 4 + 5 = 14

Find the shortest path from

A

E

by evaluating all simple paths.

A

–

B

–

C

–

D

–

E

2 + 3 + 4 + 5 = 14

A

–

B

–

C

–

E

2 + 3 + 7 = 12

A

–

B

–

D

–

E

2 + 8 + 5 = 15

A

–

C

–

E

6 + 7 = 13

A

–

C

–

D

–

E

6 + 4 + 5 = 15

Shortest path:

A

–

B

–

C

–

E

with length

12

Explain why the MST path and shortest path may differ.

The MST excluded edge

CE

(weight

7

) in favour of

DE

(weight

5

) to keep the overall tree weight as low as possible. However, for travelling from

A

E

specifically, using

CE

produces a shorter route. The MST optimises across the whole network; the shortest path optimises between two specific vertices.

Answer

(a) MST edges:

AB

BC

CD

DE

; total weight

= 14

. (b) Shortest path:

A

–

B

–

C

–

E

with length

12

. (c) The MST minimises the total weight of edges connecting all vertices, not the distance between any specific pair, so an edge excluded from the MST may still lie on the shortest path between two vertices.

Practise

Q1·Straightforward

A connected network has

7

vertices. How many edges must a spanning tree of this network contain?

Explanation

A spanning tree on

n

vertices has exactly

n - 1

edges. Here

n = 7

, so a spanning tree contains

7 - 1 = 6

edges.

Q2·Straightforward

A connected subgraph has

5

vertices and

5

edges. Is this subgraph a spanning tree?

Yes, because it is connected and contains all $5$ verticesNo, because a spanning tree on $5$ vertices must have exactly $4$ edgesYes, because the number of edges equals the number of verticesNo, because spanning trees must have fewer vertices than edges

Explanation

A spanning tree on

n

vertices must have exactly

n - 1 = 5 - 1 = 4

edges. This subgraph has

5

edges, which is one more than required. The extra edge creates a cycle, so the subgraph is not a tree.

Q3·Straightforward

Which statement correctly describes a tree in the context of networks?

A connected graph with no cyclesA disconnected graph where every vertex has the same degreeA graph that contains exactly one cycleA graph with the maximum possible number of edges

Explanation

A tree is a connected graph that contains no cycles. These two properties together mean a tree on

n

vertices has exactly

n - 1

edges.

Q4·Straightforward

A connected network has

9

vertices. A spanning tree of this network is formed by removing edges until no cycles remain and all vertices are still connected. How many edges does this spanning tree have?

Explanation

A spanning tree on

n

vertices has exactly

n - 1

edges. Here

n = 9

, so the spanning tree has

9 - 1 = 8

edges.

Q5·Moderate

A network has vertices

A

B

C

D

E

with edges

AB

(weight

4

AC

(weight

2

BC

(weight

1

BD

(weight

5

CD

(weight

3

) and

CE

(weight

4

). Find the total weight of the minimum spanning tree.

Explanation

Sorting edges by weight:

BC

(1),

AC

(2),

CD

(3),

AB

(4),

CE

(4),

BD

(5).
Add

BC

(1): connects

B

and

C

.
Add

AC

(2): connects

A

to the

B

–

C

component.
Add

CD

(3): connects

D

to the

A

–

B

–

C

component.
Skip

AB

(4):

A

and

B

are already connected — adding this edge would create a cycle.
Add

CE

(4): connects

E

. All

5

vertices are now connected.

\text{MST total weight} = 1 + 2 + 3 + 4 = 10

Q6·Moderate

A network has vertices

P

Q

R

S

T

with edges

PQ

(weight

6

PR

(weight

3

QR

(weight

4

QS

(weight

2

QT

(weight

8

RS

(weight

5

) and

ST

(weight

7

). Find the total weight of the minimum spanning tree.

Explanation

Sorting edges by weight:

QS

(2),

PR

(3),

QR

(4),

RS

(5),

PQ

(6),

ST

(7),

QT

(8).
Add

QS

(2): connects

Q

and

S

.
Add

PR

(3): connects

P

and

R

.
Add

QR

(4): connects the

\{Q, S\}

component with the

\{P, R\}

component.
Skip

RS

(5):

R

and

S

are already in the same component.
Skip

PQ

(6):

P

and

Q

are already in the same component.
Add

ST

(7): connects

T

. All

5

vertices are now connected.

\text{MST total weight} = 2 + 3 + 4 + 7 = 16

Q7·Moderate

A network has vertices

A

B

C

D

with edges

AB

(weight

7

AC

(weight

3

BC

(weight

5

BD

(weight

4

) and

CD

(weight

6

). Find the total weight of the minimum spanning tree.

Explanation

Sorting edges by weight:

AC

(3),

BD

(4),

BC

(5),

CD

(6),

AB

(7).
Add

AC

(3): connects

A

and

C

.
Add

BD

(4): connects

B

and

D

.
Add

BC

(5): connects the

\{A, C\}

component with the

\{B, D\}

component. All

4

vertices are now connected — stop.

\text{MST total weight} = 3 + 4 + 5 = 12

Q8·Moderate

A network has vertices

V

W

X

Y

Z

with edges

VW

(weight

9

VX

(weight

5

VY

(weight

7

WX

(weight

3

XY

(weight

4

XZ

(weight

6

) and

YZ

(weight

8

). Find the total weight of the minimum spanning tree.

Explanation

Sorting edges by weight:

WX

(3),

XY

(4),

VX

(5),

XZ

(6),

VY

(7),

YZ

(8),

VW

(9).
Add

WX

(3): connects

W

and

X

.
Add

XY

(4): connects

Y

to the

W

–

X

component.
Add

VX

(5): connects

V

to the

W

–

X

–

Y

component.
Add

XZ

(6): connects

Z

. All

5

vertices are now connected.

\text{MST total weight} = 3 + 4 + 5 + 6 = 18

Q9·Challenging

A network has vertices

A

B

C

D

E

with edges

AB

(weight

2

AC

(weight

6

BC

(weight

3

BD

(weight

8

CD

(weight

4

CE

(weight

7

) and

DE

(weight

5

). Find the total weight of the minimum spanning tree.

Explanation

Sorting edges by weight:

AB

(2),

BC

(3),

CD

(4),

DE

(5),

AC

(6),

CE

(7),

BD

(8).
Add

AB

(2): connects

A

and

B

.
Add

BC

(3): connects

C

to the

A

–

B

component.
Add

CD

(4): connects

D

.
Add

DE

(5): connects

E

. All

5

vertices are now connected.
Skip

AC

CE

BD

— all would create cycles or are not needed.

\text{MST total weight} = 2 + 3 + 4 + 5 = 14

Q10·Challenging

A network has vertices

A

B

C

D

E

with edges

AB

(weight

2

AC

(weight

6

BC

(weight

3

BD

(weight

8

CD

(weight

4

CE

(weight

7

) and

DE

(weight

5

). Find the length of the shortest path from

A

E

Explanation

Checking all simple paths from

A

E

A

–

B

–

C

–

D

–

E

2 + 3 + 4 + 5 = 14

A

–

B

–

C

–

E

2 + 3 + 7 = 12

(shortest)

A

–

B

–

D

–

E

2 + 8 + 5 = 15

A

–

C

–

E

6 + 7 = 13

A

–

C

–

D

–

E

6 + 4 + 5 = 15

The shortest path from

A

E

A

–

B

–

C

–

E

with length

12

Q11·Challenging

A network has vertices

P

Q

R

S

T

U

with edges

PQ

(weight

3

PR

(weight

7

QR

(weight

5

QS

(weight

4

RS

(weight

6

RT

(weight

2

ST

(weight

8

TU

(weight

3

) and

SU

(weight

9

). Find the total weight of the minimum spanning tree.

Explanation

Sorting edges by weight:

RT

(2),

PQ

(3),

TU

(3),

QS

(4),

QR

(5),

RS

(6),

PR

(7),

ST

(8),

SU

(9).
Add

RT

(2): connects

R

and

T

.
Add

PQ

(3): connects

P

and

Q

.
Add

TU

(3): connects

U

to the

R

–

T

component.
Add

QS

(4): connects

S

to the

P

–

Q

component.
Add

QR

(5): connects the

\{P, Q, S\}

component with the

\{R, T, U\}

component. All

6

vertices are now connected.

\text{MST total weight} = 2 + 3 + 3 + 4 + 5 = 17

Q12·Challenging

A network has vertices

A

B

C

D

E

with edges

AB

(weight

2

BC

(weight

3

CD

(weight

4

DE

(weight

5

CE

(weight

7

) and

AC

(weight

6

). The minimum spanning tree uses edges

AB

BC

CD

DE

and has total weight

14

. The path from

A

E

through the MST is

A

–

B

–

C

–

D

–

E

with length

14

. The shortest path from

A

E

in the full network is

A

–

B

–

C

–

E

with length

12

. Which statement best explains why the shortest path is shorter than the MST path?

The MST always uses the longest available edges in the networkThe MST minimises the total weight of all edges connecting every vertex, not the distance between specific vertices; the edge $CE$ (weight $7$) was excluded from the MST but provides a shorter route from $A$ to $E$The shortest path always avoids every edge that appears in the MSTThe MST path must pass through every vertex in the network before reaching the destination

Explanation

The MST finds the set of edges with minimum total weight that connects all vertices. It excluded

CE

(weight

7

) because

DE

(weight

5

) was cheaper for completing the tree. However, the shortest path from

A

E

only cares about the route between those two specific vertices — using

CE

gives

A

–

B

–

C

–

E = 12

, which is shorter than the MST route

A

–

B

–

C

–

D

–

E = 14