| A – B – D – F – C – E – G – A: 43 + 45 + 49 + 55 + 50 + 48 + 55 = 345 (m) | M1 | |
| A – B – D – F – G – E – C – A: 43 + 45 + 49 + 55 + 48 + 50 + 52 = 342 (m) | A1 | |
| | A1 | (3) |

**Part (b)**

| RMST weight = 237 (m) or arcs in RMST are BD, BE, BG, DF, CE; 237 + 43 + 47 = 327 (m) | B1, M1, A1 | (3) |

**Part (c)**

| $327 \leq \text{optimal distance} \leq 342$ | B1 ft | (1) |
| | | (7 marks) |

**Notes for Question 1:**

**a1M1:** First four nodes correct for a nearest neighbour route starting at A – so must have at least A – B – D – F – ... or in terms of arcs (AB, BD, DF,...) or in terms of weights (43, 45, 49,...)

**a1A1:** One correct route (in terms of arcs or nodes but not just weights), must return to A and corresponding correct length (units not required)

**a2A1:** Both routes correct (in terms of arcs or nodes but not just weights) and their corresponding correct lengths (units not required)

**b1B1:** cao for RMST weight (237) or correct arcs (BD(45), BE(46), BG(47), DF(49), CE(50) only) or 45 + 46 + 47 + 49 + 50 stated

**b1M1:** Adding the two correct least weighted arcs (AB(43) and AD(47)) to their attempt at RMST weight where their attempt at the RMST has a weight in the interval $224 < \text{RMST weight} < 250$ (give bod if not clear where their attempt at RMST weight comes from but if working shown then must be from summing the weight of exactly five arcs). Allow unsimplified answers which imply the correct two arcs added to the weight of the RMST (e.g. 45 + 46 + 47 + 49 + 50 + 43 + 47 is equivalent to the two smallest arcs (43, 47) added to five arcs which sum to a value in the given interval).

If a candidate uses one of their NN routes from (a) and removes the arcs incident to A from this route and adds on the 43 and 47 (e.g. you may see 45 + 49 + 55 + 50 + 48 + 43 + 47) then this can still score M1 as they have added the weight of five arcs that form a spanning tree (not minimal but this is their attempt - with a total in the required interval) and they have then added on the two correct least weighted arcs

**b1A1:** CAO (327) – the correct answer of 327 with no working can score all three marks in this part

**c1B1ft:** Their numbers correctly used (their answer to (b) and their least value from (a)) with correct inequalities (allow strict inequality for lower bound) so an answer of $327 – 342$ is B0. Lower bound must be less than upper bound. The LB must be $314 < \text{LB} < 340$ and is dependent on scoring the M mark in (b). The UB is dependent on the M mark in (a) and there must be two different values in (a) stated (and they must have chosen the smaller of the two). Allow equivalent notation e.g. [314, 340] or (314, 340)

**Due to the original question paper showing H in the first vertical column on the table instead of G, use the following marking guidance.**

In (a) allow use of H for G or a combination of Gs and Hs. The following are all examples that would be acceptable for the correct route A – B – D – F – C – E – G – A in (a):

- A – B – D – F – C – E – H – A
- A – B – D – F – C – E – G/H – A
- A – B – D – F – C – E – H – G – A
- A – B – D – F – C – E – G – H – G – A
- A – B – D – F – C – E – H or G – G – A
- AB, BD, DF, FC, CE, EH/G, G/HA
- AB, BD, DF, FC, CE, EG (or EH), HA (or GA)
- AB, BD, DF, FC, CE, EH, HG, GA
- AB, BD, DF, FC, CE, EH, GA

In general accept a cycle of the form A – B – D – F – C – E – X – A where X is G or H or any combination of Gs and Hs (and similarly A – B – D – F – X – E – C – A for the second cycle or their equivalents in terms of arcs).

---