The planarity algorithm and Hamiltonian cycles

The planarity algorithm and Hamiltonian cycles Test

Spec 1.4 · Edexcel A-Level Further Maths: Subtopic test

Studying this course? Keep your progress in one place.

Two ways to do this test

Question by question

One question at a time. Each answer is marked the moment you hand it in, so you learn as you go. Drago helps if you get stuck. All 10 questions, or just 5.

Exam mode

The whole paper in one go, timed like the real exam. Nothing is marked until you hand it in, then you get every mark explained.

10 questions, 27 marks

Edexcel A-Level Further Maths

The planarity algorithm and Hamiltonian cycles

Total 27 marks

Name

Class

Date

  1. 1
    A graph has six vertices AA, BB, CC, DD, EE and FF. Its edges are ABAB, BCBC, CDCD, DEDE, EFEF, FAFA, ADAD and BEBE.
    (a)
    Which of the following is a Hamiltonian cycle in this graph?
    [1 mark]
    • AA−B−C−D−AA-B-C-D-A
    • BA−B−C−D−E−F−AA-B-C-D-E-F-A
    • CA−B−C−D−E−FA-B-C-D-E-F
    • DA−B−E−F−AA-B-E-F-A
    (b)
    The planarity algorithm is applied using the cycle A−B−C−D−E−F−AA-B-C-D-E-F-A. Which statement is correct?
    [1 mark]
    • AThe graph is planar, with ADAD and BEBE both drawn inside the cycle
    • BThe graph is non-planar, because ADAD and BEBE conflict
    • CThe graph is planar, because it has a Hamiltonian cycle
    • DThe graph is planar, with ADAD inside the cycle and BEBE outside it
    (c)
    The edge CFCF is added to the graph. Use the planarity algorithm to explain whether the new graph is planar.
    [2 marks]

    Total for question 1: 4 marks

  2. 2
    A connected graph has six vertices and exactly five edges.
    (a)
    Which statement about this graph must be true?
    [1 mark]
    • AIt has a Hamiltonian cycle
    • BIt is Eulerian
    • CIt is a tree
    • DIt is a complete graph
    (b)
    A Hamiltonian cycle in a graph with six vertices contains exactly how many edges?
    [1 mark]
    • A66
    • B55
    • C77
    • D1212
    (c)
    Explain why this graph does not have a Hamiltonian cycle.
    [2 marks]

    Total for question 2: 4 marks

  3. 3
    Graph HH has vertices 11, 22, 33, 44, 55, 66 and edges 1212, 2323, 3434, 4545, 5656, 6161, 1313, 2424, 1515 and 4646. It contains the Hamiltonian cycle 1−2−3−4−5−6−11-2-3-4-5-6-1. In the planarity algorithm, two edges that are not in the cycle conflict if they cannot both be drawn on the same side of the cycle without crossing.
    (a)
    List the edges of HH that are not in the cycle, and state which pairs of them conflict.
    [3 marks]
    (b)
    Hence use the planarity algorithm to show that HH is planar, stating which edges are drawn inside the cycle and which outside.
    [4 marks]

    Total for question 3: 7 marks

  4. 4
    The complete graph K5K_5 has vertices AA, BB, CC, DD, EE and contains the Hamiltonian cycle A−B−C−D−E−AA-B-C-D-E-A. The graph K4K_4 is formed from the vertices AA, BB, CC, DD of K5K_5 and the edges joining them.
    (a)
    Use the planarity algorithm to show that K5K_5 is not planar.
    [6 marks]
    (b)
    By considering K4K_4 and K5K_5, evaluate the claim that every Eulerian graph is planar.
    [6 marks]

    Total for question 4: 12 marks

End of questions

Subtopic tests