Download IITian Academy App for accessing Online Mock Tests and More..
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, A0 for two or more.
[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; A1A1A0 for all correct, but with additions; A1A0A0 for two correct with or without additions.
[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 R1 has been given.
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, A1 for the middle vertices.
[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 R1 is awarded.
[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]