Question 1:
1 | For reference:
1 | (a) | (i) | (a sub-division of) K , is not a subgraph since there are only 5
33
vertices with degree ≥ 3
(a sub-division of) K is not a subgraph since there are only 3 vertices
5
with degree (≥) 4
Hence graph is planar | B1
B1
[2] | Explaining why K , is not a subgraph (not just stating it)
33
Explaining why K is not a subgraph (not just stating it)
5
Conclusion may be implied
SC B1 for saying 2 vertices with degree 2 but not referring
to total number of vertices
Kuratowski is asked for in question, so just describing e.g.
‘moving arc BG so that it is outside’ gets no credit
1 | (a) | (ii) | 7 + R = 11 + 2
⇒ R = 6 | B1
[1] | Correct use of V + R = E + 2 leading to answer 6
Answer 6 with no evidence of Euler ⇒ B0
1 | (b) | (i) | e.g. A – B – D – E – G – F – C – A
e.g. A – B – G – E – D – F – C – A | B1
[1] | One of these (or in reverse) with any starting point
Cycle must be closed and must pass through all 7 vertices
1 | (b) | (ii) | e.g. A and G are non-adjacent
deg(A) + deg (G) = 2 + 3 = 5 < 7 (= n) | M1
A1
[2] | Any two non-adjacent vertices and their degrees (or sum)
provided degrees sum to 5 or 6 (but not greater than 6)
Showing that degree sum is not ≥ 7 (compare with 7)
1 | (c) | (i) | B1
[1] | Graph with AB and CF contracted
(and labelled using this notation)
1 | (c) | (ii) | Only non-adjacent vertices are D and G
d eg(D) + deg(G) = 3 + 3 = 6
n = 5 vertices
and 6 is greater than 5
Hence result | M1
A1
[2] | D and G have degree sum = 6
Showing that degree sum is > 5 (compare with 5)
6 ≥ 5 or 6 > 5, or equivalent, or in words
1 | –3 | 1 | 0 | 0 | 0 | 0
1 | 0 | 1 | 1.5 | 1.5 | 0 | 27