| Date | November 2009 | Marks available | 9 | Reference code | 09N.3dm.hl.TZ0.2 |
| Level | HL only | Paper | Paper 3 Discrete mathematics | Time zone | TZ0 |
| Command term | Deduce, Determine, Find, and Show | Question number | 2 | Adapted from | N/A |
Question
The diagram below shows the weighted graph G .
(a) (i) What feature of the graph enables you to deduce that G contains an Eulerian circuit?
(ii) Find an Eulerian circuit.
(c) Use Kruskal’s Algorithm to find the minimum spanning tree for G , showing the order in which the edges are added.
Markscheme
(a) (i) all the vertices have even degree A1
(ii) for example ABCDECFBEFA A2
[3 marks]
(c) the edges are included in the order shown
M1A1A1A1A1A1
Note: Award each A1 for the edge added in the correct order. Award no further marks after the first error.
[6 marks]
Total [9 marks]
Examiners report
Part (a) was well answered in general. Part (c) was well answered.
