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}$$

\begin{enumerate}[label=(\roman*)]
\item Draw the graph $G$. [1]

\item Use Euler's formula to verify that there are four regions. Identify each region by listing the vertices that define it. [3]

\item Explain why graph $G$ cannot have a Hamiltonian cycle that includes the edge $AB$. Deduce how many Hamiltonian cycles graph $G$ has. [4]
\end{enumerate}

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.

\begin{enumerate}[label=(\roman*)]
\setcounter{enumi}{3}
\item Apply this algorithm to graph $G$, starting at $E$. Explain how the colouring shows you that graph $G$ is not bipartite. [2]
\end{enumerate}

By removing just one edge from graph $G$ it is possible to make a bipartite graph.

\begin{enumerate}[label=(\roman*)]
\setcounter{enumi}{4}
\item Identify which edge needs to be removed and write down the two sets of vertices that form the bipartite graph. [2]
\end{enumerate}

Graph $G$ is augmented by the addition of a vertex $X$ joined to each of $A$, $B$, $C$, $D$, $E$ and $F$.

\begin{enumerate}[label=(\roman*)]
\setcounter{enumi}{5}
\item Apply Kuratowski's theorem to a contraction of the augmented graph to explain how you know that the augmented graph has thickness 2. [4]
\end{enumerate}

\hfill \mbox{\textit{OCR Further Discrete 2017 Q6 [16]}}