A planar graph \(G\) is described by the adjacency matrix below.
$$\begin{pmatrix}
0 & 1 & 0 & 0 & 1 & 1 \\
1 & 0 & 1 & 0 & 1 & 0 \\
0 & 1 & 0 & 1 & 0 & 0 \\
0 & 0 & 1 & 0 & 1 & 1 \\
1 & 1 & 0 & 1 & 0 & 0 \\
1 & 0 & 0 & 1 & 0 & 0
\end{pmatrix}$$
- Draw the graph \(G\). [1]
- Use Euler's formula to verify that there are four regions. Identify each region by listing the vertices that define it. [3]
- Explain why graph \(G\) cannot have a Hamiltonian cycle that includes the edge \(AB\). Deduce how many Hamiltonian cycles graph \(G\) has. [4]
A colouring algorithm is given below.
STEP 1: Choose a vertex, colour this vertex using colour 1.
STEP 2: If all vertices are coloured, STOP. Otherwise use colour 2 to colour all uncoloured vertices for which there is an edge that joins that vertex to a vertex of colour 1.
STEP 3: If all vertices are coloured, STOP. Otherwise use colour 1 to colour all uncoloured vertices for which there is an edge that joins that vertex to a vertex of colour 2.
STEP 4: Go back to STEP 2.
- Apply this algorithm to graph \(G\), starting at \(E\). Explain how the colouring shows you that graph \(G\) is not bipartite. [2]
By removing just one edge from graph \(G\) it is possible to make a bipartite graph.
- Identify which edge needs to be removed and write down the two sets of vertices that form the bipartite graph. [2]
Graph \(G\) is augmented by the addition of a vertex \(X\) joined to each of \(A\), \(B\), \(C\), \(D\), \(E\) and \(F\).
- Apply Kuratowski's theorem to a contraction of the augmented graph to explain how you know that the augmented graph has thickness 2. [4]