(i)     Explain briefly what features of the graph enable you to state that \(G\) has an Eulerian trail but does not have an Eulerian circuit.

(ii)     Write down an Eulerian trail in \(G\) .

(i)     Use Kruskal’s algorithm to find and draw the minimum spanning tree for \(G\) . Your solution should indicate the order in which the edges are added.

(ii)     State the weight of the minimum spanning tree.

Use Dijkstra’s algorithm to find the path of minimum total weight joining A to D, and state its weight. Your solution should indicate clearly the use of this algorithm.

(i)     \(G\) has an Eulerian trail because it has \(2\) vertices of odd degree and the remaining vertices of even degree     R1

\(G\) does not have an Eulerian circuit because not all vertices are of even degree     R1

(ii)     BAFBCFECDE     A1

[3 marks]

(i)     the edges are added in the order

FE     A1

CE

AB     A1

BF, CD

or CD, BF     A1

                                                                                                                A1

(ii)     minimum weight is \(19\)     A1

[5 marks]

the shortest path is AFCD     A2

the weight is \(16\)     A1

[10 marks]

This question was attempted by the majority of students with at least partial success by most. Most candidates were able to give a partial explanation of the condition for a graph to have an Eulerian trail and not an Eulerian circuit, but few were able to provide the required detail. Most candidates were able to write down an Eulerian trail in \(G\). Many candidates successfully applied Kruskal’s algorithm and Dijkstra’s algorithm, but a number of candidates did not appreciate the significance of the order of adding edges in Kruskal’s algorithm, and the explanations of Dijkstra’s algorithm were sometimes poor.

This question was attempted by the majority of students with at least partial success by most. Most candidates were able to give a partial explanation of the condition for a graph to have an Eulerian trail and not an Eulerian circuit, but few were able to provide the required detail. Most candidates were able to write down an Eulerian trail in G. Many candidates successfully applied Kruskal’s algorithm and Dijkstra’s algorithm, but a number of candidates did not appreciate the significance of the order of adding edges in Kruskal’s algorithm, and the explanations of Dijkstra’s algorithm were sometimes poor.

This question was attempted by the majority of students with at least partial success by most. Most candidates were able to give a partial explanation of the condition for a graph to have an Eulerian trail and not an Eulerian circuit, but few were able to provide the required detail. Most candidates were able to write down an Eulerian trail in \(G\). Many candidates successfully applied Kruskal’s algorithm and Dijkstra’s algorithm, but a number of candidates did not appreciate the significance of the order of adding edges in Kruskal’s algorithm, and the explanations of Dijkstra’s algorithm were sometimes poor.