Draw \({\kappa _{3,\,3}}\).

Show that \({\kappa _{3,\,3}}\) has a Hamiltonian cycle.

Draw \({\kappa _{3,\,2}}\) and explain why it does not have a Hamiltonian cycle.

In the context of graph theory, state the handshaking lemma.

Hence show that a graph G with degree sequence 2, 3, 3, 4, 4, 5 cannot exist.

Let T be a tree with \(v\) where \(v\) ≥ 2.

Use the handshaking lemma to prove that T has at least two vertices of degree one.

     A1

[1 mark]

for example ADBECFA       A1

Note: Accept drawing the cycle on their diagram.

Note: Accept Dirac’s theorem (although it is not on the syllabus for (a)(ii). There is no converse that could be applied for (a)(iii).

[1 mark]

     A1

a Hamiltonian cycle would have to alternate between the two vertex subsets which is impossible as 2 ≠ 3      R1

Note: Award R1 for an attempt to construct a Hamiltonian cycle and an explanation of why it fails, eg, ADBEC but there is no route from C to A without re-using D or E so no cycle. There are other proofs eg, have to go in and out of A, similarly B and C giving all edges leading to a contradiction.

[2 marks]

the sum of the vertex degrees is twice the number of edges      A1

[1 mark]

assume G exists

the sum 2 + 3 + 3 + 4 + 4 + 5 = 21      A1

this is odd (not even)      R1

this contradicts the handshaking lemma

so G does not exist      AG

[2 marks]

T has \(v - 1\) edges     A1

EITHER

if \(k\) vertices have degree 1 then \(v - k\) vertices have degree ≥ 2     R1

by the handshaking lemma

\(2v - 2 \geqslant 1 \times k + 2\left( {v - k} \right)\left( { = 2v - k} \right)\)     M1

this gives \(k\) ≥ 2    A1

OR

let S be the sum of vertex degrees

consider T having either no or one vertex of degree 1       R1

case 1 suppose T has no vertices of degree 1 (eg, all vertices have degrees ≥ 2)

by the handshaking lemma

\(S \geqslant 2v \ne 2\left( {v - 1} \right)\) (not possible)      A1

case 2 suppose T has one vertex of degree 1 (eg, \(v - 1\) vertices have degrees ≥ 2)

by the handshaking lemma

\(S \geqslant 2\left( {v - 1} \right) + 1 \ne 2\left( {v - 1} \right)\) (not possible)      A1

THEN

so T has at least two vertices of degree 1     AG

[4 marks]