20N.1.AHL.TZ0.F_2

pestleMathematicsAIHLPaper 120N· ahl-3-16-tree-and-cycle-algorithms-chinese-postman-travelling-salesmansource ↗

The following diagram shows the graph $G$ .

Verify that $G$ satisfies the handshaking lemma.

[3]

Show that $G$ cannot be redrawn as a planar graph.

[3]

State, giving a reason, whether $G$ contains an Eulerian circuit.

[2]

Markscheme / solution

* This question is from an exam for a previous syllabus, and may contain minor differences in marking or structure.

METHOD 1

sum of degrees of vertices $= 3 + 5 + 5 + 5 + 4 + 4 = 26$ A1

number of edges $e = 13$ A1

the sum is equal to twice the number of edges which

verifies the handshaking lemma R1

METHOD 2

degrees of vertices $= 3, 5, 5, 5, 4, 4$ A1

there are $4$ vertices of odd order A1

there is an even number of vertices of odd order

which verifies the handshaking lemma R1

[3 marks]

if planar then $e \leq 3 v - 6$ M1

$e = 13, v = 6$ A1

inequality not satisfied R1

therefore $G$ is not planar AG

Note: method explaining that the graph contains $κ_{3, 3}$ is acceptable.

[3 marks]

there are vertices of odd degree R1

hence it does not contain an Eulerian circuit A1

Note: Do not award R0A1.

[2 marks]

Examiners’ report

[N/A]