User interface language: English | Español

Date November 2020 Marks available 3 Reference code 20N.1.AHL.TZ0.F_2
Level Additional Higher Level Paper Paper 1 Time zone Time zone 0
Command term Verify Question number F_2 Adapted from N/A

Question

The following diagram shows the graph G.

Verify that G satisfies the handshaking lemma.

[3]
a.

Show that G cannot be redrawn as a planar graph.

[3]
b.

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

[2]
c.

Markscheme

* 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]

a.

if planar then e3v-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]

b.

there are vertices of odd degree        R1

hence it does not contain an Eulerian circuit        A1


Note: Do not award R0A1.


[2 marks]

c.

Examiners report

[N/A]
a.
[N/A]
b.
[N/A]
c.

Syllabus sections

Topic 3—Geometry and trigonometry » AHL 3.16—Tree and cycle algorithms, Chinese postman, travelling salesman
Show 87 related questions
Topic 3—Geometry and trigonometry

View options