# Question 6:

## Part (a)

| Answer | Marks | Guidance |
|--------|-------|----------|
| $B - A - D - C$ | B1 | This route written |

## Part (b)

| Answer | Marks | Guidance |
|--------|-------|----------|
| Route: $A - D - E - F$ | B1 | Correct route |
| Working: $A\,\boxed{1}\,(0)$; $B\,\boxed{3}\,\boxed{3}$, $C\,\boxed{\phantom{0}}\,\boxed{7}$; $D\,\boxed{2}\,\boxed{2}$, $E\,\boxed{4}\,\boxed{5}$, $F\,\boxed{5}\,\boxed{6}$ | M1 | Use Dijkstra starting at A |
| All permanent values correct (may also see $C=7$) | A1 | |
| **Alternative:** Route $A-D-E-F$ using Dijkstra starting at $F$, all permanent values correct (may also see $C=8$) | B1, M1, A1 | |

## Question 6(c):

**MST Arcs:**
AB, AD, CD, DE, EF | M1 | A list of five valid arcs forming a tree connecting the six vertices, or a tree drawn connecting the six vertices
Arcs in MST correct (written or drawn) | A1 | Arcs in MST correct

**Shortest routes (when not a single arc):**
ADC, ADE, ADEF, BADC, BAD, BEF, CEF, DEF (or reversed) | B1 | At least two of these routes (when not a single arc). May be evidenced by sight of network or graph, or any correct pair in answer

**Pairs of villages:**
B and E, B and F, C and E, C and F | M1, A1 | M1: Any two correct pairs written in answer (and at most 6 pairs). A1: All four correct and no others (allow BE, BF, CE, CF). Ignore repeats (e.g. B and E, E and B)

**[5 marks total]**

---