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

**Answer/Explanation**

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

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?

**Answer/Explanation**

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

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

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

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

## Question

The graph *G *has adjacency matrix ** M **given below.

Draw the graph *G *.

What information about *G *is contained in the diagonal elements of * M*\(^2\) ?

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

**Answer/Explanation**

## Markscheme

* A2*

* *

**Note: **Award ** A1 **if only one error,

**for two or more.**

*A0**[2 marks]*

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

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

**Note: A1A1A1 **for three correct with no additions;

**for all correct, but with additions;**

*A1A1A0***for two correct with or without additions.**

*A1A0A0**[3 marks]*

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

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.

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.

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

(i) Does this graph have an Eulerian circuit? Justify your answer.

(ii) Does this graph have an Eulerian trail? Justify your answer.

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.

**Answer/Explanation**

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

(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

**has been given.**

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

*[4 marks]*

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

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

Fairly good knowledge shown here but not by all.

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.

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

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

(ii) State the minimum total weight.

**Answer/Explanation**

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

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

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

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.

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

Using the adjacency matrices,

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

**Answer/Explanation**

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

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

Write down an Eulerian trail in *G*.

State the Chinese postman problem.

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

Calculate the total weight of the solution.

**Answer/Explanation**

## Markscheme

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

**[1 mark]**

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

**[1 mark]**

for example BAEBCEFCDF **A1A1**

**Note:** Award * A1 *for start/finish at B/F,

*for the middle vertices.*

**A1****[2 marks]**

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

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

total weight is (65 + 15=)80 ** A1**

**[1 mark]**

## Examiners report

[N/A]

[N/A]

[N/A]

[N/A]

[N/A]

[N/A]

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

Giving a reason, state whether or not *G* is

(i) simple;

(ii) connected;

(iii) bipartite.

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

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

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.

**Answer/Explanation**

## Markscheme

* A2*

*[2 marks]*

(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

**is awarded.**

*R1** *

*[4 marks]*

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

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

*[1 mark]*

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

## Examiners report

[N/A]

[N/A]

[N/A]

[N/A]

[N/A]