Question 2:
2 | (a) | e.g. A – C – B – D – E – F – A | B1
[1] | 1.1 | A valid correct cycle (written) ) through all 6 vertices
with any starting point (which must also be shown as end point)
2 | (b) | e.g. B – C – A – D – E – F – D – B – F – A
– E – C | M1
A1
[2] | 1.1
1.2 | Any route that starts at B and ends at C, including A, D, E, F
(or starts at C and ends at B)
Any valid correct route (written) that uses every arc exactly once
Must have each letter twice
2 | (c) | {A, B, E}, {C, D, F} can be used to form
K by removing arcs AE and DF
3,3
K is a subgraph so non-planar
3,3 | M1
A1 | 2.4
2.4 | Identifying the subsets {A, B, E}, {C, D, F} or the arcs AE, DF
K and conclusion
3,3
Alternative method
Contraction of BC gives K as a subgraph
5 | M1 | Contract BC
K is a subgraph so non-planar
5 | K is a subgraph so non-planar
5 | A1 | A1 | K and conclusion
5 | K and conclusion
5
[2]
2 | (d) | Non-planar so thickness  1
Can be drawn using 2 layers e.g.
A B C A B C
D E F D E F
so thickness ≤ 2
hence thickness = 2 | B1
M1
A1
[3] | 2.1
2.1
1.1 | Thickness must be > 1 (or thickness ≥ 2) from previous result
Attempt to show how the graph can be drawn using only 2 layers
(11 arcs, allow at most one error or omission)
For reference: A B C
D E F
A correct labelled diagram or complete description using 2 layers
so thickness = 2
2 | –3 | –4 | –4