(ii)     Find the number of walks of length \(4\) beginning and ending at B.

(i)     Draw \(G'\), the complement of \(G\) .

(ii)     Write down the degrees of all the vertices of \(G\) and all the vertices of \(G'\).

(iii)     Hence, or otherwise, determine whether or not \(G\) and \(G'\) are isomorphic.

(i)     the adjacency matrix is

\(\left( {\begin{array}{*{20}{c}}
0&1&0&0&0\\
1&0&1&0&1\\
0&1&0&1&0\\
0&0&1&0&1\\
0&1&0&1&0
\end{array}} \right)\)     A2

Note: Award A2 for correct matrix, A1 for one or two errors and A0 for more than two errors.

(ii)     the required number of walks is the (B, B) element in the fourth power of the adjacency matrix     (M1) 

using a GDC gives the answer as 13     A2

[5 marks]

(i)

     A2

(ii)

     A1A1

(iii)     In \(G\), the vertex of degree 1 is adjacent to the vertex of degree 3, whereas in \(G'\) the vertex of degree \(1\) is adjacent to a vertex of degree \(2\). They are not therefore isomorphic.     A1R1

Note: Accept alternative correct solutions.

[6 marks]

Many candidates wrote down the adjacency matrix correctly and then proceeded to raise it to the fourth power, although at least one candidate actually enumerated, correctly, the \(13\) walks.

Part (b) was reasonably well done with many candidates realising that, although the degrees of the vertices were the same, their relative positions meant that the two graphs were not isomorphic.