7.02n Kuratowski's theorem: K_5 and K_{3,3} subdivisions

1 Two graphs are shown below. \begin{figure}[h] \end{figure} \begin{figure}[h] \end{figure}

1. 1. Prove that the graphs are isomorphic.
   2. Verify that Euler's formula holds for graph G1.
2. Describe how it is possible to add 4 arcs to graph G1 to make a non-planar graph with 5 vertices.
3. Describe how it is possible to add a vertex U and 4 arcs to graph G 2 to make a connected nonplanar graph with 6 vertices.

4 A connected graph is shown below. \includegraphics[max width=\textwidth, alt={}, center]{50697293-6cdc-475f-981f-71a351b0ff5a-4_442_954_296_246}

1. Write down a path through exactly 7 of the vertices.
2. Write down a cycle through exactly 6 of the vertices.
3. Explain why Ore's theorem cannot be used to decide whether or not this graph is Hamiltonian.
4. Prove that the graph is not Hamiltonian. The following colouring algorithm can be used to determine whether a connected graph is bipartite or not. The algorithm colours each vertex of a graph in one of two colours, (1) and (2). STEP 1 Choose a vertex and assign it colour (1).
   STEP 2 If any vertex is adjacent to another vertex of the same colour, stop. Otherwise assign colour (2) to each vertex that is adjacent to a vertex with colour (1).
   STEP 3 If any vertex is adjacent to another vertex of the same colour, stop. Otherwise assign colour (1) to each vertex that is adjacent to a vertex with colour (2).
   STEP 4 Repeat STEP 2 and STEP 3 until all vertices are coloured.
   STEP 5 If there are no adjacent vertices of the same colour then the graph is bipartite, output the word "bipartite".
   Otherwise the graph is not bipartite, output the words "not bipartite".
5. Use this algorithm, starting at vertex A, to determine whether the graph is bipartite, or not. [2
6. Explain what Kuratowski's theorem tells you about the graph.
7. Show that the graph has thickness 2 .

2 A graph is shown below. \includegraphics[max width=\textwidth, alt={}, center]{c4755464-aa15-4720-8f33-5eb7169f4a20-2_522_810_1637_246}

1. Write down a cycle through all six vertices.
2. Write down a continuous route that uses every arc exactly once.
3. Use Kuratowski's theorem to show that the graph is not planar.
4. Show that the graph has thickness 2 .

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.

4 One of these graphs is isomorphic to \(\mathrm { K } _ { 2,3 }\). \begin{figure}[h] \end{figure} \begin{figure}[h] \end{figure} \begin{figure}[h] \end{figure}

1. Explain how you know that each of the other graphs is not isomorphic to \(\mathrm { K } _ { 2,3 }\). The arcs of the complete graph \(\mathrm { K } _ { 5 }\) can be partitioned as the complete bipartite graph \(\mathrm { K } _ { 2,3 }\) and a graph G.
2. Draw the graph G.
3. Explain carefully how you know that the graph \(\mathrm { K } _ { 5 }\) has thickness 2 . The following colouring algorithm can be used to determine whether a connected graph is bipartite or not. The algorithm colours each vertex of a graph in one of two colours, \(\alpha\) and \(\beta\). STEP 1 Choose a vertex and assign it colour \(\alpha\).
   STEP 2 If any vertex is adjacent to another vertex of the same colour, jump to STEP 5. Otherwise assign colour \(\beta\) to each vertex that is adjacent to a vertex with colour \(\alpha\). STEP 3 If any vertex is adjacent to another vertex of the same colour, jump to STEP 5. Otherwise assign colour \(\alpha\) to each vertex that is adjacent to a vertex with colour \(\beta\). STEP 4 Repeat STEP 2 and STEP 3 until all vertices are coloured.
   STEP 5 If there are no adjacent vertices of the same colour then the graph is bipartite. Otherwise the graph is not bipartite. STEP 6 Stop.
4. Apply this algorithm to graph A, starting with the vertex in the top left corner, to determine whether graph A is bipartite or not. A measure of the efficiency of the colouring algorithm is given by the number of passes through STEP 4.
5. Write down how many passes through STEP 4 are needed for the bipartite graph \(\mathrm { K } _ { 2,3 }\). The worst case is when the graph is a path that starts at one vertex and ends at another, having passed through each of the other vertices once.
6. What can you deduce about the efficiency of the colouring algorithm in this worst case? The colouring algorithm is used on two graphs, X and Y . It takes 10 seconds to run for graph X and 60 seconds to run for graph Y. Graph X has 1000 vertices.
7. Estimate the number of vertices in graph Y . A different algorithm has efficiency \(\mathrm { O } \left( 2 ^ { n } \right)\). This algorithm takes 10 seconds to run for graph X .
8. Explain why you would expect this algorithm to take longer than 60 seconds to run for graph Y .

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)

1 Which of the following graphs is not planar? Circle your answer.
[0pt] [1 mark] \includegraphics[max width=\textwidth, alt={}, center]{88669bc0-9d3f-431a-8939-8aef2682412b-02_186_301_1000_520} \includegraphics[max width=\textwidth, alt={}, center]{88669bc0-9d3f-431a-8939-8aef2682412b-02_218_224_986_884} \includegraphics[max width=\textwidth, alt={}, center]{88669bc0-9d3f-431a-8939-8aef2682412b-02_241_236_982_1201} \includegraphics[max width=\textwidth, alt={}, center]{88669bc0-9d3f-431a-8939-8aef2682412b-02_241_241_982_1521}

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.

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}

The organiser of a sponsored walk wishes to allocate each of six volunteers, Alan, Geoff, Laura, Nicola, Philip and Sam to one of the checkpoints along the route. Two volunteers are needed at checkpoint 1 (the start) and one volunteer at each of checkpoint 2, 3, 4 and 5 (the finish). Each volunteer will be assigned to just one checkpoint. The table shows the checkpoints each volunteer is prepared to supervise. Initially Alan, Geoff, Laura and Nicola are assigned to the first checkpoint in their individual list.

1. Draw a bipartite graph to model this situation and indicate the initial matching in a distinctive way. [2]
2. Starting from this initial matching, use the maximum matching algorithm to find an improved matching. Clearly list any alternating paths you use. [3]
3. Explain why it is not possible to find a complete matching. [2]

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

\includegraphics{figure_3} \includegraphics{figure_4} A film critic, Verity, must see five films A, B, C, D and E over two days. The films are being shown at five special critics' preview times: \begin{align} 1 &\text{ (Monday 4 pm),}
2 &\text{ (Monday 7 pm),}
3 &\text{ (Tuesday 1 pm),}
4 &\text{ (Tuesday 4 pm),}
5 &\text{ (Tuesday 7 pm).} \end{align} The bipartite graph in Figure 3 shows the times at which each film is showing. Initially Verity intends to see \begin{align} &\text{Film A on Monday at 4 pm,}
&\text{Film B on Tuesday at 4 pm,}
&\text{Film C on Tuesday at 1 pm,}
&\text{Film D on Monday at 7 pm.} \end{align} This initial matching is shown in Figure 4. Using the maximum matching algorithm and the given initial matching,

1. find two distinct alternating paths and complete the matchings they give. [6]

Verity's son is very keen to see film D, but he can only go with his mother to the showing on Monday at 7 pm.

1. Explain why it will not be possible for Verity to take her son to this showing and still see all five films herself. [2]

(Total 8 marks)

\includegraphics{figure_1} \includegraphics{figure_2} Six workers, Annie, Emma, Hannah, Jerry, Louis and Morand, are to be assigned to five tasks, 1,2,3,4 and 5. For safety reasons, task 1 must be done by two people working together. A bipartite graph showing the possible allocations of the workers is given in Figure 1 and an initial matching is given in Figure 2. The maximum matching algorithm will be used to obtain a complete matching.

1. Although there are five tasks, six vertices have been created on the right hand side of each bipartite graph. Explain why this is necessary when applying this algorithm. [2]
2. Find an alternating path and the complete matching it gives. [3]

Hannah is now unable to do task 5 due to health reasons.

1. Explain why a complete matching is no longer possible. [2]

(Total 7 marks)

The graph \(G\) has a subgraph isomorphic to \(K_5\), the complete graph with 5 vertices. Which of the following statements about \(G\) must be true? Tick \((\checkmark)\) one box. [1 mark] \(G\) is not connected \(G\) is not Hamiltonian \(G\) is not planar \(G\) is not simple

The graph below connects nine vertices A, B, \(\ldots\), H, I. \includegraphics{figure_2}

1. 1. Show that the minimum sum of the degrees of each pair of non-adjacent vertices is 9. [2]
   2. Explain what you can deduce from the result in part (a). [1]
2. Use Kuratowski's theorem to prove that the graph is non-planar. [3]
3. Prove that there is no subgraph of the graph that is isomorphic to \(K_4\), without using subdivision or contraction. [6]