4 One of these graphs is isomorphic to \(\mathrm { K } _ { 2,3 }\).
\begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{133395d2-5020-4054-a229-70168f1d0f95-5_175_195_285_242}
\captionsetup{labelformat=empty}
\caption{Graph A}
\end{figure}
\begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{133395d2-5020-4054-a229-70168f1d0f95-5_170_195_285_635}
\captionsetup{labelformat=empty}
\caption{Graph B}
\end{figure}
\begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{133395d2-5020-4054-a229-70168f1d0f95-5_168_191_287_1027}
\captionsetup{labelformat=empty}
\caption{Graph C}
\end{figure}
- 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.
- Draw the graph G.
- 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. - 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.
- 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.
- 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.
- 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 .
- Explain why you would expect this algorithm to take longer than 60 seconds to run for graph Y .