# IB DP Maths Topic 10.8 Walks, trails, paths, circuits, cycles HL Paper 3

## Question

The diagram below shows the graph G with vertices A, B, C, D, E and F.

(i)     Determine if any Hamiltonian cycles exist in G . If so, write one down.

Otherwise, explain what feature of G makes it impossible for a Hamiltonian cycle to exist.

(ii)     Determine if any Eulerian circuits exist in G . If so, write one down.

Otherwise, explain what feature of G makes it impossible for an Eulerian circuit to exist.

## Markscheme

(i)     any Hamiltonian circuit ACBEFDA     A2

(ii)     no Eulerian circuit exists because the graph contains vertices of odd degree     A2

[4 marks]

## Examiners report

Parts (a) and (b) were well answered by many candidates. In (c), candidates who tried to prove the result by adding edges to a drawing of G were given no credit. Candidates should be aware that the use of the word ‘Prove’ indicates that a formal treatment is required Solutions to (d) were often disappointing although a graphical solution was allowed here.

## Question

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.

[5]
a.

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?

[12]
b.

## Markscheme

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

a.

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

b.

## Examiners report

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).

a.

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).

b.

## Question

The graph G has adjacency matrix M given below.

Draw the graph G .

[2]
a.

What information about G is contained in the diagonal elements of M$$^2$$ ?

[1]
b.

List the trails of length 4 starting at A and ending at C.

[3]
d.

## Markscheme

A2

Note: Award A1 if only one error, A0 for two or more.

[2 marks]

a.

the (k, k) element of M$$^2$$ is the number of vertices directly connected to vertex k     A1

Note: Accept comment about the number of walks of length 2, in which the initial and final vertices coincide.

[1 mark]

b.

the trails of length 4 are ABEDC, AFEDC, AFEBC     A1A1A1

Note: A1A1A1 for three correct with no additions; A1A1A0 for all correct, but with additions; A1A0A0 for two correct with or without additions.

[3 marks]

d.

## Examiners report

Parts (a) and (c) were generally correctly answered. In part (b), a minority of candidates failed to mention that the starting and end points had to coincide. A large number of candidates gave all walks (trails were asked for) – an unnecessary loss of marks.

a.

Parts (a) and (c) were generally correctly answered. In part (b), a minority of candidates failed to mention that the starting and end points had to coincide. A large number of candidates gave all walks (trails were asked for) – an unnecessary loss of marks.

b.

Parts (a) and (c) were generally correctly answered. In part (b), a minority of candidates failed to mention that the starting and end points had to coincide. A large number of candidates gave all walks (trails were asked for) – an unnecessary loss of marks.

d.

## Question

In the graph given above, the numbers shown represent the distance along that edge.

Using Dijkstra’s algorithm, find the length of the shortest path from vertex S to vertex T . Write down this shortest path.

[6]
a.

[4]
b.

The graph above is now to be considered with the edges representing roads in a town and with the distances being the length of that road in kilometres. Huan is a postman and he has to travel along every road in the town to deliver letters to all the houses in that road. He has to start at the sorting office at S and also finish his route at S . Find the shortest total distance of such a route. Fully explain the reasoning behind your answer.

[4]
c.

## Markscheme

from tabular method as shown above (or equivalent)     M1A1A1

Note: Award the first A1 for obtaining 3 as the shortest distance to C.

Award the second A1 for obtaining the rest of the shortest distances.

shortest path has length 17     A1

backtracking as shown above (or equivalent)     (M1)

shortest path is SABT     A1

[6 marks]

a.

(i)     no, as S and T have odd degree     A1R1

Note: Mentioning one vertex of odd degree is sufficient.

(ii)     yes, as only S and T have odd degree     A1R1

Note: In each case only award the A1 if the R1 has been given.

Accept an actual trail in (b)(ii).

[4 marks]

b.

Huan has to travel along all the edges via an open Eulerian trail of length     R1

4 + 3 + 5 + 2 + 1 + 3 + 5 + 4 + 7 + 8 + 5 + 6 + 7 + 6 + 6 + 8 + 9 = 94     A1

and then back to S from T along the shortest path found in (a) of length 17     R1

so shortest total distance is 94 + 17 = 111     A1

[4 marks]

c.

## Examiners report

This was quite well answered. Some candidates did not make their method clear and others showed no method at all. Some clearly had a correct method but did not make it clear what their final answers were. It is recommended that teachers look at the tabular method with its backtracking system as shown in the mark scheme as an efficient way of tackling this type of problem.

a.

Fairly good knowledge shown here but not by all.

b.

Some good answers but too much confusion with methods they partly remembered about the travelling salesman problem. Candidates should be aware of helpful connections between parts of a question.

c.

## Question

The diagram shows a weighted graph with vertices A, B, C, D, E, F, G. The weight of each edge is marked on the diagram.

(i)     Explain briefly why the graph contains an Eulerian trail but not an Eulerian circuit.

(ii)     Write down an Eulerian trail.

[4]
a.

(i)     Use Dijkstra’s algorithm to find the path of minimum total weight joining A to D.

(ii)     State the minimum total weight.

[8]
b.

## Markscheme

(i)     there is an Eulerian trail because there are only 2 vertices of odd degree     R1

there is no Eulerian circuit because not all vertices have even degree     R1

(ii)     eg GBAGFBCFECDE     A2

[4 marks]

a.

(i)

$$\begin{array}{*{20}{l}} {{\text{Step}}}&{{\text{Vertices labelled}}}&{{\text{Working values}}}&{} \\ 1&{\text{A}}&{{\text{A(0), B-3, G-2}}}&{{\boldsymbol{M1A1}}} \\ 2&{{\text{A, G}}}&{{\text{A(0), G(2), B-3, F-8}}}&{{\boldsymbol{A1}}} \\ 3&{{\text{A, G, B}}}&{{\text{A(0), G(2), B(3), F-7, C-10}}}&{{\boldsymbol{A1}}} \\ 4&{{\text{A, G, B, F}}}&{{\text{A(0), G(2), B(3), F(7), C-9, E-12}}}&{} \\ 5&{{\text{A, G, B, F, C}}}&{{\text{A(0), G(2), B(3), F(7), C(9), E-10, D-15}}}&{{\boldsymbol{A1}}} \\ 6&{{\text{A, G, B, F, C, E}}}&{{\text{A(0), G(2), B(3), F(7), C(9), E(10), D-14}}}&{} \\ 7&{{\text{A, G, B, F, C, E, D}}}&{{\text{A(0), G(2), B(3), F(7), C(9), E(10), D(14)}}}&{{\boldsymbol{A1}}} \end{array}$$

Note: In both (i) and (ii) accept the tabular method including back tracking or labels by the vertices on a graph.

Note: Award M1A1A1A1A0A0 if final labels are correct but intermediate ones are not shown.

(ii)     minimum weight path is ABFCED     A1

minimum weight is 14     A1

Note: Award the final two A1 marks whether or not Dijkstra’s Algorithm is used.

[8 marks]

b.

## Examiners report

In part (a) the criteria for Eulerian circuits and trails were generally well known and most candidates realised that they must start/finish at G/E. Candidates who could not do (a) generally struggled on the paper.

a.

For part (b) the layout varied greatly from candidate to candidate. Not all candidates made their method clear and some did not show the temporary labels. It is recommended that teachers look at the tabular method with its backtracking system as it is an efficient way of tackling this type of problem and has a very clear layout.

b.

## Question

The following figure shows the floor plan of a museum.

(a)     (i)     Draw a graph G that represents the plan of the museum where each exhibition room is represented by a vertex labelled with the exhibition room number and each door between exhibition rooms is represented by an edge. Do not consider the entrance foyer as a museum exhibition room.

(ii)     Write down the degrees of the vertices that represent each exhibition room.

(iii)     Virginia enters the museum through the entrance foyer. Use your answers to (i) and (ii) to justify why it is possible for her to visit the thirteen exhibition rooms going through each internal doorway exactly once.

(b)     Let G and H be two graphs whose adjacency matrices are represented below.

(i)     find the number of edges of each graph;

(ii)     show that exactly one of the graphs has a Eulerian trail;

(iii)     show that neither of the graphs has a Eulerian circuit.

## Markscheme

(a) (i)
(M1)A1

Note: Do not penalize candidates who include the entrance foyer.

(ii)     the degrees of the vertices are 4, 2, 4, 4, 2, 2, 4, 2, 2, 2, 2, 2, 2     A1

(iii)     the degree of all vertices is even and hence a Eulerian circuit exists,     A1

hence it is possible to enter the museum through the foyer and visit each room 1–13 going through each internal doorway exactly once     AG

Note: The connected graph condition is not required.

[4 marks]

(b)     (i)
(M1)

graph G has 15 edges and graph H has 22 edges     A1A1

(ii)     the degree of every vertex is equal to the sum of the numbers in the corresponding row (or column) of the adjacency table

exactly two of the vertices of G have an odd degree (B and C)     A1

H has four vertices with odd degree     A1

G is the graph that has a Eulerian trail (and H does not)     R1

(iii)     neither graph has all vertices of even degree     R1

therefore neither of them has a Eulerian circuit     AG

[7 marks]

## Examiners report

Part (a) was generally well answered. There were many examples of full marks in this part. Part (b) caused a few more difficulties, although there were many good solutions. Few candidates used the matrix to find the number of edges, preferring instead to draw the graph. A surprising number of students confused the ideas of having vertices of odd degree.

## Question

Consider the following weighted graph G.

State what feature of G ensures that G has an Eulerian trail.

[1]
a.i.

State what feature of G ensures that G does not have an Eulerian circuit.

[1]
a.ii.

Write down an Eulerian trail in G.

[2]
b.

State the Chinese postman problem.

[2]
c.i.

Starting and finishing at B, find a solution to the Chinese postman problem for G.

[3]
c.ii.

Calculate the total weight of the solution.

[1]
c.iii.

## Markscheme

G has an Eulerian trail because it has (exactly) two vertices (B and F) of odd degree      R1

[1 mark]

a.i.

G does not have an Eulerian circuit because not all vertices are of even degree      R1

[1 mark]

a.ii.

for example BAEBCEFCDF      A1A1

Note: Award A1 for start/finish at B/F, A1 for the middle vertices.

[2 marks]

b.

to determine the shortest route (walk) around a weighted graph      A1

using each edge (at least once, returning to the starting vertex)      A1

Note: Correct terminology must be seen. Do not accept trail, path, cycle or circuit.

[2 marks]

c.i.

we require the Eulerian trail in (b), (weight = 65)     (M1)

and the minimum walk FEB (15)     A1

for example BAEBCEFCDFEB    A1

Note: Accept EB added to the end or FE added to the start of their answer in (b) in particular for follow through.

[3 marks]

c.ii.

total weight is (65 + 15=)80      A1

[1 mark]

c.iii.

[N/A]

a.i.

[N/A]

a.ii.

[N/A]

b.

[N/A]

c.i.

[N/A]

c.ii.

[N/A]

c.iii.

## Question

The graph G has vertices P , Q , R , S , T and the following table shows the number of edges joining each pair of vertices.

Draw the graph G as a planar graph.

[2]
a.

Giving a reason, state whether or not G is

(i)     simple;

(ii)     connected;

(iii)     bipartite.

[4]
b.

Explain what feature of G enables you to state that it has an Eulerian trail and write down a trail.

[2]
c.

Explain what feature of G enables you to state it does not have an Eulerian circuit.

[1]
d.

Find the maximum number of edges that can be added to the graph G (not including any loops or further multiple edges) whilst still keeping it planar.

[4]
e.

## Markscheme

A2

[2 marks]

a.

(i)     G is not simple because 2 edges join P to T     R1

(ii)     G is connected because there is a path joining every pair of vertices     R1

(iii)     (P, R) and (Q, S, T) are disjoint vertices     R1

so G is bipartite     A1

Note: Award the A1 only if the R1 is awarded.

[4 marks]

b.

G has an Eulerian trail because it has two vertices of odd degree (R and T have degree 3), all the other vertices having even degree     R1

the following example is such a trail

TPTRSPQR     A1

[2 marks]

c.

G has no Eulerian circuit because there are 2 vertices which have odd degree     R1

[1 mark]

d.

consider

so it is possible to add 3 extra edges     A1

consider G with one of the edges PT deleted; this is a simple graph with 6 edges; on addition of the new edges, it will still be simple     M1

$$e \leqslant 3v – 6 \Rightarrow e \leqslant 3 \times 5 – 6 = 9$$     R1

so at most 3 edges can be added     R1

[4 marks]

e.

[N/A]

a.

[N/A]

b.

[N/A]

c.

[N/A]

d.

[N/A]

e.