7.02h Hamiltonian paths: and cycles

7 A simply connected graph has 6 vertices and 10 arcs.

1. What is the maximum vertex degree? You are now given that the graph is also Eulerian.
2. Explaining your reasoning carefully, show that exactly two of the vertices have degree 2 .
3. Prove that the vertices of degree 2 cannot be adjacent to one another.
4. Use Kuratowski's theorem to show that the graph is planar.
5. Show that it is possible to make a non-planar graph by the addition of one more arc. A digraph is created from a simply connected graph with 6 vertices and \(10 \operatorname { arcs }\) by making each arc into a single directed arc.
6. What can be deduced about the indegrees and outdegrees?
7. If a Hamiltonian cycle exists on the digraph, what can be deduced about the indegrees and outdegrees? \section*{OCR} \section*{Oxford Cambridge and RSA}

2 Two simply connected graphs are shown below. \begin{figure}[h] \end{figure} \begin{figure}[h] \end{figure}

1. 1. Write down the orders of the vertices for each of these graphs.
   2. How many ways are there to allocate these vertex degrees to a graph with vertices \(\mathrm { P } , \mathrm { Q }\), \(\mathrm { R } , \mathrm { S } , \mathrm { T }\) and U ?
   3. Use the vertex degrees to deduce whether the graphs are Eulerian, semi-Eulerian or neither.
2. Show that graphs 1 and 2 are not isomorphic.
3. 1. Write down a Hamiltonian cycle for graph 1.
   2. Use Euler's formula to determine the number of regions for graph 1.
   3. Identify each of these regions for graph 1 by listing the cycle that forms its boundary.

8

1. The diagram shows a graph \(\mathbf { G }\) with 9 vertices and 9 edges. \includegraphics[max width=\textwidth, alt={}, center]{e47eb41e-0a4b-4865-a8ff-6c9978495ee0-08_188_204_411_708} \includegraphics[max width=\textwidth, alt={}, center]{e47eb41e-0a4b-4865-a8ff-6c9978495ee0-08_184_204_415_1105} \includegraphics[max width=\textwidth, alt={}, center]{e47eb41e-0a4b-4865-a8ff-6c9978495ee0-08_183_204_612_909}
   1. State the minimum number of edges that need to be added to \(\mathbf { G }\) to make a connected graph. Draw an example of such a graph.
   2. State the minimum number of edges that need to be added to \(\mathbf { G }\) to make the graph Hamiltonian. Draw an example of such a graph.
   3. State the minimum number of edges that need to be added to \(\mathbf { G }\) to make the graph Eulerian. Draw an example of such a graph.
2. A complete graph has \(n\) vertices and is Eulerian.
   1. State the condition that \(n\) must satisfy.
   2. In addition, the number of edges in a Hamiltonian cycle for the graph is the same as the number of edges in an Eulerian trail. State the value of \(n\).

4

1. In the complete graph \(\mathrm { K } _ { 7 }\), every one of the 7 vertices is connected to each of the other 6 vertices by a single edge. Find or write down:
   1. the number of edges in the graph;
   2. the number of edges in a minimum spanning tree;
   3. the number of edges in a Hamiltonian cycle.
2. 1. Explain why the graph \(\mathrm { K } _ { 7 }\) is Eulerian.
   2. Write down the condition for \(\mathrm { K } _ { n }\) to be Eulerian.
3. A connected graph has 6 vertices and 10 edges. Draw an example of such a graph which is Eulerian.

7

1. A simple connected graph has 4 edges and \(m\) vertices. State the possible values of \(m\).
2. A simple connected graph has \(n\) edges and 4 vertices. State the possible values of \(n\).
3. A simple connected graph, \(G\), has 5 vertices and is Eulerian but not Hamiltonian. Draw a possible graph \(G\).
   [0pt] [2 marks]

1 The famous fictional detective Agatha Parrot is investigating a murder. She has identified six suspects: Mrs Lemon \(( L )\), Prof Mulberry \(( M )\), Mr Nutmeg \(( N )\), Miss Olive \(( O )\), Capt Peach \(( P )\) and Rev Quince \(( Q )\). The table shows the weapons that could have been used by each suspect.

1. Draw a bipartite graph to represent this information. Put the weapons on the left-hand side and the suspects on the right-hand side. Agatha Parrot is convinced that all six suspects were involved, and that each used a different weapon. She originally thinks that the axe handle was used by Prof Mulberry, the broomstick by Miss Olive, the drainpipe by Mrs Lemon, the fence post by Mr Nutmeg and the golf club by Capt Peach. However, this would leave the hammer for Rev Quince, which is not a possible pairing.
2. Draw a second bipartite graph to show this incomplete matching.
3. Construct the shortest possible alternating path from \(H\) to \(Q\) and hence find a complete matching. Write down which suspect used each weapon.
4. Find a different complete matching in which none of the suspects used the same weapon as in the matching from part (iii).

2 The graph \(G\) has 5 vertices and 6 edges, as shown below. \includegraphics[max width=\textwidth, alt={}, center]{21ed3b4e-a089-4607-b5d6-69d8aac03f31-03_547_547_360_749} Which of the following statements describes the properties of \(G\) ?
Tick ( \(\checkmark\) ) one box. \(G\) is Eulerian and Hamiltonian. □ \(G\) is Eulerian but not Hamiltonian. □ \(G\) is semi-Eulerian and Hamiltonian. □ \(G\) is semi-Eulerian but not Hamiltonian. □

\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)