D1 January 2007 Q3
3.
(a) Write down the name given to the type of graph drawn in Figure 3. (1)
A Hamiltonian cycle for the graph in Figure 3 begins A, 3, B, … .
(b) Complete this Hamiltonian cycle. (2)
(c) Starting with the Hamiltonian cycle found in (b), use the planarity algorithm to determine if the graph is planar. (3)
| Scheme | Marks |
|---|---|
| A bipartite graph | B1 |
| (1) |
| Scheme | Marks |
|---|---|
| A, 3, B, 4, C, 1, D, 2, A | B2,1,0 |
| (2) |
| Scheme | Marks |
|---|---|
Redrawing | M1 A1 |
| Identifying that it is not planar | A1ft |
| (3) | |
| (6 marks) |