User interface language: English | Español

Date May 2017 Marks available 1 Reference code 17M.3.AHL.TZ0.Hdm_3
Level Additional Higher Level Paper Paper 3 Time zone Time zone 0
Command term Explain Question number Hdm_3 Adapted from N/A

Question

In the context of graph theory, explain briefly what is meant by a circuit;

[1]
a.i.

In the context of graph theory, explain briefly what is meant by an Eulerian circuit.

[1]
a.ii.

The graph G has six vertices and an Eulerian circuit. Determine whether or not its complement G can have an Eulerian circuit.

[3]
b.

Find an example of a graph H , with five vertices, such that H and its complement H both have an Eulerian trail but neither has an Eulerian circuit. Draw H and H as your solution.

[4]
c.

Markscheme

a circuit is a walk that begins and ends at the same vertex and has no repeated edges     A1

[1 mark]

a.i.

an Eulerian circuit is a circuit that contains every edge of a graph     A1

[1 mark]

a.ii.

if G has an Eulerian circuit all vertices are even (are of degree 2 or 4)     A1

hence, G must have all vertices odd (of degree 1 or 3)     R1

hence, G cannot have an Eulerian circuit     R1

 

Note:     Award A1 to candidates who begin by considering a specific G and G (diagram). Award R1R1 to candidates who then consider a general G and G .

 

[3 marks]

b.

for example

M17/5/MATHL/HP3/ENG/TZ0/DM/M/03.c

A2

A2

 

Notes:     Each graph must have 3 vertices of order 2 and 2 odd vertices. Award A2 if one of the graphs satisfies that and the final A2 if the other graph is its complement.

 

[4 marks]

c.

Examiners report

[N/A]
a.i.
[N/A]
a.ii.
[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