# Question 3:

## Part (a)
| Answer | Mark | Guidance |
|--------|------|----------|
| AB ($x$), BC (27), BE (19), EF (20), AG (30), DG (25) | M1 | For first 4 arcs correct (with AB chosen first) |
| | A1 | All 6 arcs correct in order |

## Part (b)
| Answer | Mark | Guidance |
|--------|------|----------|
| Double the MST and add a return arc: $2(x + 27 + 19 + 20 + 30 + 25) = 2(121 + x)$ giving upper bound of $242 + 2x$ | B1ft | Follow through their MST doubled |

## Part (c)
| Answer | Mark | Guidance |
|--------|------|----------|
| A→B ($x$), B→E (19), E→F (20), F→G (49), G→D (25), D→C (24), C→A (41); Total = $x + 178$ | M1 | Correct application of nearest neighbour from A |
| | A1 | Correct route and total |

## Part (d)
| Answer | Mark | Guidance |
|--------|------|----------|
| Route from F: $F–E–B–A–G–D–C–F = 20+19+x+30+25+24+35 = 153+x$ | B1 | Correct total for F route |
| The route starting at F gives a better upper bound as $153+x < x+178$ | B1 | Correct comparison with reason |

## Part (e)
| Answer | Mark | Guidance |
|--------|------|----------|
| Lower bound = MST (minus A) + two shortest arcs from A | M1 | Correct method shown |
| MST of remaining network + shortest two arcs from A: $159 = \text{MST}_{-A} + x + 21$ | M1 | Setting up equation |
| $x = 159 - 21 - \text{(sum of MST arcs without A)}$; solving gives $x = 23$ | A1 | $x = 23$ |

## Part (f)
| Answer | Mark | Guidance |
|--------|------|----------|
| $159 \leqslant L \leqslant 176$ | B1ft | Correct lower bound 159 |
| | B1ft | Correct upper bound (their better upper bound with $x=23$) |

---