Question
The diagram above shows the graph \(G\).
(i) Explain briefly why \(G\) has no Eulerian circuit.
(ii) Determine whether or not \(G\) is bipartite.
(iii) Write down the adjacency matrix of G. Hence find the number of walks of length \(4\) beginning at A and ending at C.
The cost adjacency matrix of a graph with vertices P, Q, R, S, T, U is given by
Use Dijkstra’s Algorithm to find the length of the shortest path between the vertices P and S. Show all the steps used by the algorithm and list the order of the vertices in the path.
Answer/Explanation
Markscheme
(i) Because the graph has vertices of odd degree. R2
(ii) We are looking for \(2\) disjoint sets. (M1)
Put A in Set 1. Then B and D have to go in Set 2. This means that E and C have to go in Set 1. Therefore the disjoint sets are \(\left\{ {{\rm{B,D}}} \right\}\) and \(\left\{ {{\rm{A,C,E}}} \right\}\) . All the edges join a vertex from one set to a vertex in the other set. R2
The graph is bipartite. A1
(iii)
\({\boldsymbol{M}} = \left( {\begin{array}{*{20}{c}}
0&2&0&1&0 \\
2&0&1&0&2 \\
0&1&0&1&0 \\
1&0&1&0&1 \\
0&2&0&1&0
\end{array}} \right)\)
We require the (\(1\), \(3\)) or (\(3\), \(1\)) element of \({\boldsymbol{M}^4}\) . M1M1
Using a GDC, the number of walks of length \(4\) is \(36\). A2
[12 marks]
The length of the shortest path is \(18\). A2
EITHER
P U Q T R S A2
OR
P U Q T S A2
[12 marks]
Question
The graph \(G\) has the following cost adjacency matrix.
Draw \(G\) in planar form.
Given that \(ax \equiv b(\bmod p)\) where \(a,b,p,x \in {\mathbb{Z}^ + }\) , \(p\) is prime and \(a\) is not a multiple of \(p\), use Fermat’s little theorem to show that
\(x \equiv {a^{p – 2}}b(\bmod p)\) .
Hence solve the simultaneous linear congruences\[3x \equiv 4(\bmod 5)\]\[5x \equiv 6(\bmod 7)\]giving your answer in the form \(x \equiv c(\bmod d)\) .
Answer/Explanation
Markscheme
A2
[2 marks]
Note: The weights are not required for this A2.
Multiply through by \({a^{p – 2}}\) .
\({a^{p – 1}}x \equiv {a^{p – 2}}b(\bmod p)\) M1A1
Since, by Fermat’s little theorem, \({a^{p – 1}} \equiv 1(\bmod p)\) , R1
\(x \equiv {a^{p – 2}}b(\bmod p)\) AG
[3 marks]
Using the result from (a),
\(x \equiv {3^3} \times 4(\bmod 5) \equiv 3(\bmod 5)\) M1A1
\( = 3\), \(8\), \(13\), \(18\), \(23\),… (A1)
and \(x \equiv {5^5} \times 6(\bmod 7) \equiv 4(\bmod 7)\) M1A1
\( = 4\), \(11\), \(18\), \(25\),… (A1)
The general solution is
\(x = 18 + 35n\) M1
i.e. \(x \equiv 18(\bmod 35)\) A1
[8 marks]
Question
A canal system divides a city into six land masses connected by fifteen bridges, as shown in the diagram below.
Draw a planar graph to represent this map.
Write down the adjacency matrix of the graph.
List the degrees of each of the vertices.
State with reasons whether or not this graph has
(i) an Eulerian circuit;
(ii) an Eulerian trail.
Find the number of walks of length \(4\) from E to F.
Answer/Explanation
Markscheme
A2
[2 marks]
A2
Note: Award A1 for one error or omission, A0 for more than one error or omission. Two symmetrical errors count as one error.
[2 marks]
A B C D E F
(8, 4, 4, 3, 5, 6) A2
[2 marks]
(i) no, because there are odd vertices M1A1
(ii) yes, because there are exactly two odd vertices M1A1
[4 marks]
number of walks of length \(4\) is \(170\) (M1)A1
Note: The complete matrix need not be shown. Only one of the FE has to be shown.
[2 marks]
Question
The graph \(H\) has the following adjacency matrix.
(i) Show that \(H\) is bipartite.
(ii) Draw \(H\) as a planar graph.
(i) Explain what feature of \(H\) guarantees that it has an Eulerian circuit.
(ii) Write down an Eulerian circuit in \(H\) .
(i) Find the number of different walks of length five joining A to B.
(ii) Determine how many of these walks go through vertex F after passing along two edges.
Find the maximum number of extra edges that can be added to \(H\) while keeping it simple, planar and bipartite.
Find the smallest positive integer \(m\) such that \({3^m} \equiv 1(\bmod 22)\) .
Given that \({3^{49}} \equiv n(\bmod 22)\) where \(0 \le n \le 21\) , find the value of \(n\) .
Solve the equation \({3^x} \equiv 5(\bmod 22)\) .
Answer/Explanation
Markscheme
(i) using any method, (M1)
find that \(\left\{ {{\rm{A,C,D,F}}} \right\}\) and \(\left\{ {{\rm{B,E,G}}} \right\}\) are disjoint sets of vertices A1
so that \(H\) is bipartite AG
(ii)
A1
[3 marks]
(i) all vertices are of even degree A1
(ii) DECBAGFBD A2
[3 marks]
(i)
M1
number of walks \( = 36\) A1
(ii) recognition of the need to find walks of length \(2\) and walks of length \(3\) (M1)
number of walks of length \(2\) from A to F \( = 2\) A1
number of walks of length \(3\) from F to B \( = 6\) A1
required number of walks \( =12\) A1
[6 marks]
for a simple, bipartite graph to be planar,
\(e \le 2v – 4 = 10\) M1
at the moment, \(e = 8\) which means that we cannot add more than \(2\) edges A1
we see that we can add \(2\) edges, e.g. EA and EF A1
the maximum number of edges we can add is therefore \(2\) A1
[4 marks]
evaluating successive powers of \(3\) (M1)
\({3^1} \equiv 3(\bmod 22)\) , \({3^2} \equiv 9(\bmod 22)\) , \({3^3} \equiv 5(\bmod 22)\)
\({3^4} \equiv 15(\bmod 22)\) , \({3^5} \equiv 1(\bmod 22)\) so \(m = 5\) A1
[2 marks]
since \({3^5} \equiv 1(\bmod 22)\) , \({3^{45}} = {({3^5})^9} \equiv 1(\bmod 22)\) M1A1
consider \({3^{49}} = {3^{45}} \times {3^4} \equiv 1 \times 15(\bmod 22)\) so \(n = 15\) M1A1
[4 marks]
from (a), \(x = 3\) is a solution A1
since \({3^5} \equiv 1(\bmod 22)\) , the complete solution is \(x = 3 + 5N\) where \(N \in \bullet \) (M1)A1
[3 marks]
Question
A group of people: Andrew, Betty, Chloe, David, Edward, Frank and Grace, has certain mutual friendships:
Andrew is friendly with Betty, Chloe, David and Edward;
Frank is friendly with Betty and Grace;
David, Chloe and Edward are friendly with one another.
(i) Draw the planar graph \(H\) that represents these mutual friendships.
(ii) State how many faces this graph has.
Determine, giving reasons, whether \(H\) has
(i) a Hamiltonian path;
(ii) a Hamiltonian cycle;
(iii) an Eulerian circuit;
(iv) an Eulerian trail.
Verify Euler’s formula for \(H\) .
State, giving a reason, whether or not \(H\) is bipartite.
Write down the adjacency matrix for \(H\) .
David wishes to send a message to Grace, in a sealed envelope, through mutual friends.
In how many different ways can this be achieved if the envelope is passed seven times and Grace only receives it once?
Answer/Explanation
Markscheme
(i)
A2
Note: Award A1 if one error made.
(ii) \(4\) A1
[3 marks]
(i) yes, for example GFBACDE A1R1
(ii) no, for example F and B would be visited twice A1R1
(iii) no, because the graph contains vertices of odd degree A1R1
(iv) no, because there are more than two vertices of odd degree A1R1
Note: The A and R marks can be considered as independent.
[8 marks]
\(v = 7\) , \(e = 9\) A1
\(f = 4\) from (a)(ii)
\(9 + 2 = 7 + 4\) R1AG
[2 marks]
no, because the graph contains at least one triangle A1R1
[2 marks]
\(\left( {\begin{array}{*{20}{c}}
{}&{\text{A}}&{\text{B}}&{\text{C}}&{\text{D}}&{\text{E}}&{\text{F}}&{\text{G}} \\
{\text{A}}&0&1&1&1&1&0&0 \\
{\text{B}}&1&0&0&0&0&1&0 \\
{\text{C}}&1&0&0&1&1&0&0 \\
{\text{D}}&1&0&1&0&1&0&0 \\
{\text{E}}&1&0&1&1&0&0&0 \\
{\text{F}}&0&1&0&0&0&0&1 \\
{\text{G}}&0&0&0&0&0&1&0
\end{array}} \right)\) A2
Note: A1 for one error, A0 for more than one error.
[2 marks]
METHOD 1
DG element of 7th power of matrix \( = 26\) M1A1A1
Note: M1 for attempt at some power; A1 for 7th power; A1 for \(26\).
DG element of the 5th power of the matrix \( = 2\) A1A1
obtain \(26 – 2 = 24\) M1A1
METHOD 2
the observation that letter has to reach Grace after Frank obtains it after \(6\) passings, (without Grace having received it earlier) (M1)(A1)
statement that the G row and column have been deleted A1A1
DF element of 6th power of new matrix is \(24\) M1A1A1
Note: M1 for attempt at some power of new or old matrix; A1 for 6th power of new matrix; A1 for 24.
[7 marks]
Question
While on holiday Pauline visits the local museum. On the ground floor of the museum there are six rooms, A, B, C, D, E and F. The doorways between the rooms are indicated on the following floorplan.
There are 6 museum s in 6 towns in the area where Pauline is on holiday. The 6 towns and the roads connecting them can be represented by a graph. Each vertex represents a town, each edge represents a road and the weight of each edge is the distance between the towns using that road. The information is shown in the adjacency table.
Pauline wants to visit each town and needs to start and finish in the same town.
Draw a graph G to represent this floorplan where the rooms are represented by the vertices and an edge represents a door between two rooms.
Explain why the graph G has an Eulerian trail but not an Eulerian circuit.
Explain the consequences of having an Eulerian trail but not an Eulerian circuit, for Pauline’s visit to the ground floor of the museum.
Write down a Hamiltonian cycle for the graph G.
Explain the consequences of having a Hamiltonian cycle for Pauline’s visit to the ground floor of the museum.
Use the nearest-neighbour algorithm to determine a possible route and an upper bound for the length of her route starting in town Z.
By removing Z, use the deleted vertex algorithm to determine a lower bound for the length of her route.
Answer/Explanation
Markscheme
A2
[2 Marks]
two vertices are of odd degree A1
to have an Eulerian circuit it must have all vertices of even degree R1
hence no Eulerian circuit, but an Eulerian trail AG
[2 Marks]
it allows Pauline to go through every door once (provided she starts in
room B or room E) A1
and she cannot return to the room in which she started A1
[2 Marks]
for example: A → F → E → D → C → B → A A2
Note: Award A1 if the cycle does not return to the start vertex.
[2 Marks]
she can visit every room once without repeating and return to the start A1
[1 Mark]
Z → V → Y → X → U → W → Z A1
6 + 4 + 9 + 7 + 10 + 10 = 46 A1
[2 marks]
attempt to find the minimal spanning tree (M1)
VY
VW
UX
XY A2
Note: Award A1 if one error made.
Note: Accept correct drawing of minimal spanning tree.
weight of minimal spanning tree = 4 + 5 + 7 + 9 = 25 (A1)
since Z is removed, we add on VZ and ZY (M1)
hence lower bound for route is 25 + 13 = 38 A1
[6 marks]
Question
A connected planar graph has \(e\) edges, \(f\) faces and \(v\) vertices. Prove Euler’s relation, that is \(v + f = e + 2\) .
(i) A simple connected planar graph with \(v\) vertices, where \(v \ge 3\) , has no circuit of length \(3\). Deduce that \(e \ge 2f\) and therefore that \(e \le 2v – 4\).
(ii) Hence show that \({\kappa _{3,3}}\) is non-planar.
The graph \(P\) has the following adjacency table, defined for vertices A to H, where each element represents the number of edges between the respective vertices.
(i) Show that \(P\) is bipartite.
(ii) Show that the complement of \(P\) is connected but not planar.
Answer/Explanation
Markscheme
consider the basic graph with just \(1\) vertex for which \(v = 1\) , \(f = 1\) and \(e = 0\)
for this case, \(v + f = e + 2 = 2\) so the result is true here M1A1
Note: Allow solutions which begin with a graph containing \(2\) vertices and an edge joining them for which \(v = 2\) , \(f = 1\) and \(e = 1\) .
a graph can be extended as follows – there are three cases to consider
I – an extra edge is added joining two distinct existing vertices R1
II – an extra edge is added joining an existing vertex to itself, forming a loop R1
in each case v remains the same and \(f\) and \(e\) each increase by \(1\)
both sides of the equation increase by \(1\) and the equation still holds R1
III – an extra vertex is added together with an edge joining this new vertex to an existing vertex (which is necessary to keep the graph connected) R1
in this case, \(f\) remains the same and \(v\) and \(e\) each increase by \(1\)
both sides of the equation increase by \(1\) and the equation still holds R1
any graph can be constructed from the basic graph by combining these operations, all of which result in Euler’s relation remaining valid R1
[8 marks]
(i) since the graph is simple there are no loops and no multiple edges and thus no circuits of length \(1\) or \(2\) R1
as we are told that there are no circuits of length 3, any face must be surrounded by at least \(4\) edges R1
since every edge is adjacent to \(2\) faces, R1
\(2e = \sum {({\text{degrees of faces}}) \ge 4f} \) , A1
it follows that \(e \ge 2f\) AG
using Euler’s relation with \(f \le \frac{e}{2}\) , M1
\(f = e – v + 2 \le \frac{e}{2}\) A1
giving \(e \le 2v – 4\) AG
(ii) \({\kappa _{3,3}}\) is simple and since it is bipartite it has no cycles of length \(3\) R1
for \({\kappa _{3,3}}\) , \(v = 6\) and \(e = 9\) A1
\(2v – 4 = 8\) so that the above inequality is not satisfied R1
it follows that \({\kappa _{3,3}}\) is not planar AG
[9 marks]
(i) attempt to find disjoint sets of vertices (M1)
disjoint sets are {A, D, G, H} and {B, C, E, F} A1
Note: Accept graph with vertices coloured, or otherwise annotated.
(ii) let \(P’\) denote the complement of P
in \(P’\) , A is connected to D, E, F, G and H : B and C are connected to E
therefore A is connected to all other vertices so \(P’\) is connected M1A1
a complete graph with \(8\) vertices has \(28\) edges A1
since \(P\) has \(9\) edges, \(P’\) has \(19\) edges A1
consider \(e \le 3v – 6\) (the condition for a planar graph) M1
for \({P’}\) , \(e = 19\) ; \(3v – 6 = 18\) so the condition is not satisfied A1
therefore \({P’}\) is not planar AG
[8 marks]