Planarity algorithm application

1. \begin{figure}[h] \end{figure}

1. Find a Hamiltonian cycle for the graph shown in Figure 1.
2. Starting with your cycle, construct a plane drawing of the graph, showing your method clearly.
   (5 marks)

1 This question is about the planar graph shown below. \includegraphics[max width=\textwidth, alt={}, center]{cc58fb7a-efb6-4548-a8e1-e40abe1eb722-2_567_1317_395_374}

1. 1. Apply Kuratowski's theorem to verify that the graph is planar.
   2. Use Euler's formula to calculate the number of regions in a planar representation of the graph.
2. 1. Write down a Hamiltonian cycle for the graph.
   2. By finding a suitable pair of vertices, show that Ore's theorem cannot be used to prove that the graph, as shown above, is Hamiltonian.
3. 1. Draw the graph formed by using the contractions AB and CF .
   2. Use Ore's theorem to show that this contracted graph is Hamiltonian.

1. Figure 1 \includegraphics[max width=\textwidth, alt={}, center]{438a62e6-113c-428e-85bf-4b1cbecee0de-2_473_682_348_614}

A Hamilton cycle for the graph in Fig. 1 begins \(A , X , D , V , \ldots\).

1. Complete this Hamiltonian cycle.
2. Hence use the planarity algorithm to determine if the graph is planar.

2. An electronics company makes a product that consists of components \(A , B , C , D , E\) and \(F\). The table shows which components must be connected together to make the product work. The components are all placed on a circuit board and connected by wires, which are not allowed to cross.

1. On the diagram in the answer book draw straight lines to show which components need to be connected.
   (1)
2. Starting with the Hamiltonian cycle \(A B C D E F A\), use the planarity algorithm to determine whether it is possible to build this product on a circuit board.
   (4)

2. (a) Define the following terms

1. planar graph,
2. Hamiltonian cycle.
   (b) (i) Draw a graph of \(\mathrm { K } _ { 3,2 }\) in such a way as to show that it is planar.
3. Explain why the planarity algorithm cannot be used when drawing \(\mathrm { K } _ { 3,2 }\) as a planar graph.

1. \begin{figure}[h] \end{figure} A Hamiltonian cycle for the graph in Figure 1 begins \(\mathrm { C } , \mathrm { V } , \mathrm { E } , \mathrm { X } , \mathrm { A } , \mathrm { W } , \ldots\).

1. Complete the Hamiltonian cycle.
2. Hence use the planarity algorithm to determine whether the graph shown in Figure 1 is planar. You must make your working clear and justify your answer.

2. \begin{figure}[h] \end{figure}

1. Define what is meant by a planar graph.
2. Starting at A, find a Hamiltonian cycle for the graph in Figure 1. Arc AG is added to Figure 1 to create the graph shown in Figure 2. \begin{figure}[h]
   \includegraphics[alt={},max width=\textwidth]{37435cc9-1e38-4c55-bd72-e2a1ec415ba7-03_568_666_1226_701} \captionsetup{labelformat=empty} \caption{Figure 2}
   \end{figure} Taking ABCDEFGA as the Hamiltonian cycle,
3. use the planarity algorithm to determine whether the graph shown in Figure 2 is planar. You must make your working clear and justify your answer.

\includegraphics{figure_1} Use the planarity algorithm to show that the graph in Fig. 1 is planar. [4]

\includegraphics{figure_3}

1. 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, ....

1. Complete this Hamiltonian cycle. (2)
2. Starting with the Hamiltonian cycle found in (b), use the planarity algorithm to determine if the graph is planar. (3)

(Total 6 marks)

\includegraphics{figure_1}

1. Starting from \(A\); write down a Hamiltonian cycle for the graph in Figure 1. [2]
2. 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.

1. Explain why the new graph is not planar. [2]

(Total 7 marks)