4 A connected graph is shown below.
\includegraphics[max width=\textwidth, alt={}, center]{50697293-6cdc-475f-981f-71a351b0ff5a-4_442_954_296_246}
- Write down a path through exactly 7 of the vertices.
- Write down a cycle through exactly 6 of the vertices.
- Explain why Ore's theorem cannot be used to decide whether or not this graph is Hamiltonian.
- 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". - Use this algorithm, starting at vertex A, to determine whether the graph is bipartite, or not. [2
- Explain what Kuratowski's theorem tells you about the graph.
- Show that the graph has thickness 2 .