7.02o Thickness: of graphs

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 .

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 .