| Answer/Working | Marks | Guidance |
|---|---|---|
| e.g. (each arc contributes 1 to the orders of two nodes, and so) the sum of the orders of all the nodes is equal to twice the number of arcs. Which implies that the sum of the orders of all the nodes is even and therefore there must be an even (or zero) number of vertices of odd order hence there cannot be an odd number of vertices of odd order | B2, 1, 0 | (2) |
| Prim: AB, AD, BC, DE; | M1; A1; A1 | |
| | EF, FG; | | |
| | GI, HJ | | |
| Weight = 92 (mins) | B1 | (4) |
| $20x + 17 +$ repeat arcs $= 162$ B and E are the only two odd nodes so must be paired $4x + 3$ (BE) is clearly greater in value than $x + (2x + 3) + (x - 1) = 4x + 2$ (AB, AD, DE) so repeated arcs are either AB, AD, DE ($4x + 2$) or BC, CE ($7x - 17$) $4x + 2 = 7x - 17 \Rightarrow x = 19/3$ $x < 19/3 \Rightarrow 20x + 7x - 17 = 145 \therefore x = 143/24 < 19/3$ so $x \ne 143/24$ | B1 | |
| | B1 | |
| | B1 | |
| | M1 A1 | (6) |
| | **12 marks** | |

**Notes for Question 6:**

- **a1B1**: For one of the following points:
  - 'Sum of the order/valencies of the nodes/vertices $= 2($number of arcs/edges)'
  - 'Each arc/edge contributes 1 to the order/valency of two nodes/vertices'
  - 'Sum of the order/valencies of the nodes/vertices is even'

But condone for B1 only:
  - 'sum of the valencies $= 2($number of arcs/edges)' or 'sum of the nodes/vertices $= 2($number of arcs/edges)' or 'sum of the orders $= 2($number of arcs/edges)'
  - 'sum of the valencies is even' or 'sum of the nodes/edges is even'

- **a2B1**: stating that 'the sum of the order (or valencies) of the nodes/vertices $= 2($number of arcs/edges) therefore the sum of the order (of the nodes/vertices) is even which implies that there must be an even number of nodes/vertices of odd order (or there cannot be an odd number of nodes/vertices of odd order)' OR each arc/edge contributes 1 to the order of two nodes/vertices therefore the sum of the order (of the nodes/vertices) is even which implies that there must be an even number of nodes/vertices of odd order (or there cannot be an odd number of nodes/vertices of odd order).

**So in summary the first B mark should be awarded for a broadly correct statement (but allow bod as shown in the last two bullet-points above) but for both B marks a fully correct explanation must be given without any bod (please note therefore it is not possible to score B0B1). Do not accept non-technical language for nodes/arcs for either B1B0 or B1B1.**

- **biIM1**: Prim – First four arcs (AB, AD, BC, DE) correctly chosen, or first five nodes (A, B, D, C, E) correctly chosen in order. If any explicit rejections seen at any point then M1 marks only. A list of weights only scores M0. Candidates may apply Prim's in matrix form so the order of the nodes may be seen at the top of a matrix – accept {1,2,4,3,5,...} for the M mark. Allow CB for BC etc. throughout (b).
- **biIA1**: First six arcs correctly chosen in order (AB, AD, BC, DE, EF, FG), or all nodes correctly chosen in order (A, B, D, C, E, F, G, I, J, H). Candidates may apply Prim's in matrix form so the order of the nodes may be seen at the top of a matrix – accept {1,2,4,3,5,6,7,9,8} – do not condone any missing numbers e.g. the number 9 must be above H.
- **biIA1**: CSO (correct solution only) – all arcs correctly stated and chosen in the correct order. Candidates must be considering arcs for this final mark (do not accept a list of nodes or numbers across the top of the matrix unless the correct list of arcs (in the correct order) is also seen).

**Misread**: Starting at a node other than A scores M1 only in (b)(i) – must have the first four arcs (or five nodes) correct (and in the correct order).

- **biiB1**: CAO (92) – condone lack of units.
- **c1B1**: Consideration of B and E (as odd nodes) – this mark can be implied by considering the pairing of B with E at any point (need not see explicit reference to B and E e.g. one correct equation in $x$ would imply this mark)
- **c2B1**: Explicit consideration of why BE cannot be the least pairing of B with E – candidates must clearly reject with a reason why the arc BE is not the shortest path between B and E. As a minimum accept both expressions stated correctly in the form $4x + b$ and then BE $>$ BADE or $4x + 3 > 4x + 2$ but B0 if just stating both expressions and selecting $4x + 2$ without any reason given – do not award this mark if any of the expressions for BE or BADE are stated incorrectly.
- **c3B1**: Consideration for what values of $x$ either of the two other paths would be least – so for this mark we must see the value of 19/3 or 6.333… (to at least 3 s.f. or equivalent) as either the solution to the linear equation $4x + 2 = 7x - 17$ or as a solution to an inequality involving these two linear expressions.
- **c1M1**: Correct equation in $x$ for any of the three possible pairings of B with E – so for this mark only accept $20x + 17 + 4x + 3 = 162$ or $20x + 17 + x - 1 + x + 2x + 3 = 162$ or $20x + 17 + 2x - 4 + 5x - 13 = 162$ (or equivalent) - any of these three equations would imply the first B mark (consideration of B and E as odd nodes).
- **c1A1**: CAO (for $x = 6$) – this must come from the correct equation $20x + 7x - 17 = 162$ and not from rounding 5.9583… or 5.9166… - allow this mark even if 143/24 (or equivalent e.g. 5.9583…) or 71/12 (or equivalent e.g. 5.9166…) is given as a possible solution too.
- **c2A1**: Correctly shows that the pairings of AB, AD and DE does not give a consistent value for $x$ – as a minimum for this mark the candidate must explicitly state that 143/24 or 5.9583… (to at least 3 s.f.) **is less than 19/3 or 6.333…** (to at least 3 s.f.) **and so therefore** $x$ **cannot take the value of 143/24 or 5.9583…** (either mathematically or in words).

---