D1 June 2005 Q2
2.
(a) Starting from \(A\); write down a Hamiltonian cycle for the graph in Figure 1. (2)
(b) Use the planarity algorithm to show that the graph in Figure 1 is planar. (3)
Arcs \(AF\) and \(EF\) are now added to the graph.
(c) Explain why the new graph is not planar. (2)
| Scheme | Marks |
|---|---|
| e.g. \(AEBFCDA\) | M1 A1 |
| (2) |
| Scheme | Marks |
|---|---|
e.g. | M1 A1 A1 |
| (3) |
| Scheme | Marks |
|---|---|
| State that one of these arcs (\(AF\) or \(EF\)) [Named], crosses at least one arc in each set. [Named arcs] | B2,1,0 |
| (2) | |
| (7 marks) |