Determine whether or not $G$ is bipartite.

(i)     Write down the adjacency matrix for $G$.

(ii)     Find the number of distinct walks of length $4$ beginning and ending at A.

$G$ is bipartite     A1

because it contains a triangle.     R1

Note: Award R1 for a valid attempt at showing that the vertices cannot be divided into two disjoint sets.

[2 marks]

(i)

${\boldsymbol{M}} = \left( {\begin{array}{*{20}{c}}   0&1&0&0&0&1 \\   1&0&1&1&1&0 \\   0&1&0&1&0&0 \\   0&1&1&0&1&1 \\   0&1&0&1&0&1 \\   1&0&0&1&1&0 \end{array}} \right)$     A1

(ii)     We require the (A, A) element of ${\boldsymbol{M}^4}$ which is $13$.     M1A2

[4 marks]