In any graph, show that

(i)     the sum of the degrees of all the vertices is even;

(ii)     there is an even number of vertices of odd degree.

Consider the following graph, M.

(i)     Show that M is planar.

(ii)     Explain why M is not Eulerian.

(iii)     By adding one edge to M it is possible to make it Eulerian. State which edge must be added.

This new graph is called N.

(iv)     Starting at A, write down a possible Eulerian circuit for N.

(v)     Define a Hamiltonian cycle. If possible, write down a Hamiltonian cycle for N, and if not possible, give a reason.

(vi)     Write down the adjacency matrix for N.

(vii)     Which pair of distinct vertices has exactly 30 walks of length 4 between them?

(i)     When we sum over the degrees of all vertices, we count each edge twice. Hence every edge adds two to the sum. Hence the sum of the degrees of all the vertices is even.     R2

(ii)     divide the vertices into two sets, those with even degree and those with odd degree     M1

let S be the sum of the degrees of the first set and let T be the sum of the degrees of the second set

we know S + T must be even

since S is the sum of even numbers, then it is even     R1

hence T must be even     R1

hence there must be an even number of vertices of odd degree     AG

[5 marks]

(i)

    A1

(ii)     the graph M is not Eulerian because vertices D and F are of odd degree     A1

(iii)     the edge which must be added is DF     A1

(iv)

a possible Eulerian circuit is ABDFBCDEFGCA     A2

Note: award A1 for a correct Eulerian circuit not starting and finishing at A.

(v)     a Hamiltonian cycle is one that contains each vertex in N     A1

with the exception of the starting and ending vertices, each vertex must only appear once     A1

a possible Hamiltonian cycle is ACGFEDBA     A1

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

(vii)     using adjacency matrix to power 4     (M1)

C and F     A1 

[12 marks]

Most candidates were able to start (a), but many found problems in expressing their ideas clearly in words. Stronger candidates had little problem with (b), but a significant number of weaker candidates had problems working with the concepts of Eulerian circuits and Hamiltonian cycles and with understanding how to find a specific number of walks of a certain length as required in (b) (vii).

Most candidates were able to start (a), but many found problems in expressing their ideas clearly in words. Stronger candidates had little problem with (b), but a significant number of weaker candidates had problems working with the concepts of Eulerian circuits and Hamiltonian cycles and with understanding how to find a specific number of walks of a certain length as required in (b) (vii).