**Part (a)**

| E.g. You cannot have a graph with an odd number of odd vertices | B1 | (1) |

**Part (b)**

| E.g. $\frac{1+2+2+3+3+4+4+6}{2}=12.5$ which is not an integer and so therefore not possible to have a graph with the given vertex orders | B2, 1, 0 | (2) |

**Part (c)**

| AC, AB, CD; DH, DG, CF, DE | M1; A1; A1 | (3) |

**Part (d)**

| [Graph diagram showing the required structure] | B1 | (1) |

**Part (e)**

| $21 < x < 25$ | B2, 1, 0 | (2) |

| | | (9 marks) |

**Notes for Question 5:**

**a1B1:** CAO – common examples that score B1:
- Cannot have (a graph with an) odd number of odd vertices
- Cannot have a graph with three odd vertices
- The sum of the degrees/order (of the vertices) is 25 which is not even therefore not possible (but not just for obtaining 25 and saying 'impossible'). The 25 must be linked either in words to the 'sum of the degrees/order' or explicitly showing $1+2+2+3+3+4+4+6=25$ so just '25 is not even' scores B0
- The sum of the degrees/order (of the vertices) is 25 which is odd therefore not possible (with equivalent justification of the 25 as in the previous bullet-point)
- $\frac{1+2+2+3+3+4+4+6}{2}=12.5$ which is not an integer so therefore impossible. They do not have to explain that they are using the result that $\sum \text{vertex degrees} = 2(\text{no of arcs})$ but they must explain why a value of 12.5 leads to the required graph not being possible. A value of 12.5 with no working (or explanation) scores B0

**b1B1:** No + attempt at a reason which includes **either the mention of a cycle/circle/loop etc. or the repeating of a vertex/node/point etc.** is sufficient for this mark (condone incorrect technical language) – give bod ('but' not because there is a repeated 'arc' only scores B0 unless we also mention of a repeated vertex (oe) as well)

**b2DB1:** No + correct reason (dependent on first B mark in (b)) – no bod – must refer to C appearing twice (not just that a vertex is repeated) or that it contains the cycle C – D – E – C (not just that it contains a cycle). **All technical language must be correct if used for this mark and do not isw any incorrect reasoning**

The minimum acceptable answer for both marks in this part is, 'it is not a path as C appears twice'

**c1M1:** Prim's – first three arcs correctly chosen in order (AC, AB, CD) or first four nodes (A, C, B, D) correctly chosen in order. **If any explicit rejections seen at some point then M1 (max) only**. Order of nodes may be seen at the top of a matrix/table {1, 3, 2, 4, -, -, -, -}. However, do not accept a list of weights only (as the weights in the network are not unique)

**c1A1:** First five arcs correctly chosen in order (AC, AB, CD, DH, DG) or all eight nodes {A, C, B, D, H, G, F, E} correctly chosen in order. Order of nodes may be seen at the top of a matrix so for the first two marks accept {1, 3, 2, 4, 8, 7, 6, 5} (no missing numbers). However, do not accept a list of weights only (as the weights in the network are not unique)

**c2A1:** CSO – all arcs correctly stated and chosen in the correct order (with no additional incorrect arcs). They must be considering arcs for this final mark (do not accept a list of the weights of each arc, nodes or numbers across the top of the matrix unless the correct list of arcs (in the correct order) is also seen)

**Misread in (c):** Starting at a node other than A scores **M1 only** – must have the first three arcs (or four nodes) correct (and in the correct order) – condone any rejections seen for this mark

**d1B1:** CAO (ignore weights on arcs even if incorrect)

**e1B1:** $x < 25$ or $x \leq 25$ or $x < 24$ or $x \leq 24$ or equivalent notation e.g. $(\ldots, 25)$

**e2B1:** CAO ($21 < x < 25$) or equivalent notation (e.g. $(21, 25)$)

---