Question
$G$ is a simple, connected graph with eight vertices.
$H$ is a connected, planar graph, with $v$ vertices, $e$ edges and $f$ faces. Every face in $H$ is bounded by exactly $k$ edges.
a.i. Write down the minimum number of edges in $G$.
a.ii.Find the maximum number of edges in $G$.
a.iiiFind the maximum number of edges in $G$, given that $G$ contains an Eulerian circuit.
b.i.Explain why $2 e=k f$.
b.iiFind the value of $f$ when $v=9$ and $k=3$.
b.iiiEind the possible values of $f$ when $v=13$.
▶️Answer/Explanation
a.i. 7 (a tree)
A1
[1 mark]
a.ii. $\frac{8 \times 7}{2}(7+6+5+4+3+2+1)$ (a complete graph) (M1)
$=28$
A1
[2 marks]
a.iii: $\frac{8 \times 6}{2}$ (since every vertex must be of degree 6) (M1)
$=24$
A1
[2 marks]
b.i. counting the edges around every face gives $k f$ edges
A1
but as every edge is counted in 2 faces
R1
$\Rightarrow k f=2 e \quad$ AG
[2 marks]
b.ii.using $v-e+f=2$ with $v=9 \quad$ M1
EITHER
substituting $2 e=3 f$ into $2(9)-2 e+2 f=4 \quad$ (M1)
OR
substituting $e=\frac{3 f}{2}$ into $9-e+f=2$
(M1)
THEN
$$
18-f=4
$$
$f=14$
A1
b.iii2 $v-k f+2 f=4$ (or equivalent) M1
when $v=13$
$(k-2) f=22$ or $(2-k) f=-22$
A1
EITHER
$$
(k-2) f=1 \times 2 \times 11 \quad \text { M1 }
$$
OR
substituting at least two of $k=13,4,3$ into $f=\frac{22}{k-2}$ (or equivalent) $\quad M 1$
THEN
$f=2,11,22$ (since $f>1)$
A1
[4 marks]
Question
This question is about a metropolitan area council planning a new town and the location of a new toxic waste dump.
A metropolitan area in a country is modelled as a square. The area has four towns, located at the corners of the square. All units are in kilometres with the $x$-coordinate representing the distance east and the $y$-coordinate representing the distance north from the origin at $(0,0)$.
– Edison is modelled as being positioned at $\mathrm{E}(0,40)$.
– Fermitown is modelled as being positioned at $\mathrm{F}(40,40)$.
– Gaussville is modelled as being positioned at $\mathrm{G}(40,0)$.
– Hamilton is modelled as being positioned at $\mathrm{H}(0,0)$.
The metropolitan area council decides to build a new town called Isaacopolis located at I(30, 20).
A new Voronoi diagram is to be created to include Isaacopolis. The equation of the perpendicular bisector of [IE] is $y=\frac{3}{2} x+\frac{15}{2}$.
The metropolitan area is divided into districts based on the Voronoi regions found in part (c).
A toxic waste dump needs to be located within the metropolitan area. The council wants to locate it as far as possible from the nearest town.
The toxic waste dump, $\mathrm{T}$, is connected to the towns via a system of sewers.
The connections are represented in the following matrix, $\boldsymbol{M}$, where the order of rows and columns is (E, F, G, H, I, T).
$$
\boldsymbol{M}=\left(\begin{array}{llllll}
1 & 0 & 1 & 1 & 0 & 0 \\
0 & 1 & 0 & 0 & 0 & 1 \\
1 & 0 & 1 & 0 & 1 & 0 \\
1 & 0 & 0 & 1 & 0 & 1 \\
0 & 0 & 1 & 0 & 1 & 0 \\
0 & 1 & 0 & 1 & 0 & 1
\end{array}\right)
$$
A leak occurs from the toxic waste dump and travels through the sewers. The pollution takes one day to travel between locations that are directly connected.
The digit 1 in $\boldsymbol{M}$ represents a direct connection. The values of 1 in the leading diagonal of $\boldsymbol{M}$ mean that once a location is polluted it will stay polluted
a. The model assumes that each town is positioned at a single point. Describe possible circumstances in which this modelling assumption is reasonable.
b. Sketch a Voronoi diagram showing the regions within the metropolitan area that are closest to each town.
c.i. Find the equation of the perpendicular bisector of [IF].
c.ii.Given that the coordinates of one vertex of the new Voronoi diagram are $(20,37.5)$, find the coordinates of the other two vertices within the metropolitan area.
c.iiiSketch this new Voronoi diagram showing the regions within the metropolitan area which are closest to each town.
d. A car departs from a point due north of Hamilton. It travels due east at constant speed to a destination point due North of Gaussville. It passes through the Edison, Isaacopolis and Fermitown districts. The car spends $30 \%$ of the travel time in the Isaacopolis district.
Find the distance between Gaussville and the car’s destination point.
e.i. Find the location of the toxic waste dump, given that this location is not on the edge of the metropolitan area.
e.ii.Make one possible criticism of the council’s choice of location.
f.i. Find which town is last to be polluted. Justify your answer.
f.ii. Write down the number of days it takes for the pollution to reach the last town.
f.iii.A sewer inspector needs to plan the shortest possible route through each of the connections between different locations. Determine an appropriate start point and an appropriate end point of the inspection route.
Note that the fact that each location is connected to itself does not correspond to a sewer that needs to be inspected.
▶️Answer/Explanation
a. the size of each town is small (in comparison with the distance between the towns)
OR
if towns have an identifiable centre
OR
the centre of the town is at that point $\quad \boldsymbol{R 1}$
Note: Accept a geographical landmark in place of “centre”, e.g. “town hall” or “capitol”.
b.
c.i. the gradient of IF is $\frac{40-20}{40-30}=2$
(A1)
negative reciprocal of any gradient
(M1)
gradient of perpendicular bisector $=\frac{1}{2}$
Note: Seeing $-\frac{2}{3}$ (for example) used clearly as a gradient anywhere is evidence of the “negative reciprocal” method despite being applied to an inappropriate gradient.
midpoint is $\left(\frac{40+30}{2}, \frac{40+20}{2}\right)=(35,30)$
(A1)
equation of perpendicular bisector is $y-30=-\frac{1}{2}(x-35)$
A1
Note: Accept equivalent forms e.g. $y=-\frac{1}{2} x+\frac{95}{2}$ or $2 y+x-95=0$.
Allow FT for the final $\boldsymbol{A 1}$ from their midpoint and gradient of perpendicular bisector, as long as the $\boldsymbol{M 1}$ has been awarded
[4 marks]
c.ii.the perpendicular bisector of $\mathrm{EH}$ is $y=20$
(A1)
Note: Award this A1 if seen in the $y$-coordinate of any final answer or if 20 is used as the $y$-value in the equation of any other perpendicular bisector.
attempt to use symmetry OR intersecting two perpendicular bisectors
(M1)
$\left(\frac{25}{3}, 20\right) \quad \boldsymbol{A 1}$
(20, 2.5) $\quad \boldsymbol{A 1}$
[4 marks ]
c.iii.
d. $30 \%$ of 40 is 12
(A1)
recognizing line intersects bisectors at $y=c$ (or equivalent) but different $x$-values
(M1)
$c=\frac{3}{2} x_1+\frac{15}{2}$ and $c=-\frac{1}{2} x_2+\frac{95}{2}$
finding an expression for the distance in Isaacopolis in terms of one variable
(M1)
$$
x_2-x_1=(95-2 c)-\frac{2 c-15}{3}=100-\frac{8 c}{3}
$$
equating their expression to 12
$$
\begin{aligned}
& 100-\frac{8 c}{3}=0.3 \times 40=12 \\
& c=33
\end{aligned}
$$
distance $=33(\mathrm{~km}) \quad$ A1
e.i. must be a vertex (award if vertex given as a final answer)
(R1)
attempt to calculate the distance of at least one town from a vertex
(M1)
Note: This must be seen as a calculation or a value.
correct calculation of distances
A1
$\frac{65}{3}$ OR 21.7 AND $\sqrt{406.25}$ OR 20.2
$\left(\frac{25}{3}, 20\right) \quad$ A1
Note: Award R1MOAOAO for a vertex written with no other supporting calculations.
Award R1MOAOA1 for correct vertex with no other supporting calculations.
The final $\boldsymbol{A 1}$ is not dependent on the previous $\boldsymbol{A 1}$. There is no follow-through for the final $\boldsymbol{A 1}$.
Do not accept an answer based on “uniqueness” in the question.
[4 marks]
e.ii.For example, any one of the following:
decision does not take into account the different population densities
closer to a city will reduce travel time/help employees
it is closer to some cites than others
R1
Note: Accept any correct reason that engages with the scenario.
Do not accept any answer to do with ethical issues about whether toxic waste should ever be dumped, or dumped in a metropolitan area.
f.i. METHOD 1
attempting $\boldsymbol{M}^3 \quad \boldsymbol{M 1}$
attempting $\boldsymbol{M}^4 \quad \boldsymbol{M 1}$
e.g.
last row/column of $M^3=\left(\begin{array}{llllll}3 & 5 & 1 & 6 & 0 & 7\end{array}\right)$
last row/column of $\boldsymbol{M}^4=\left(\begin{array}{llllll}10 & 12 & 4 & 16 & 1 & 18\end{array}\right)$
hence Isaacopolis is the last city to be polluted
A1
Note: Do not award the $\boldsymbol{A} 1$ unless both $\boldsymbol{M}^3$ and $\boldsymbol{M}^4$ are considered.
Award M1MOAO for a claim that the shortest distance is from $T$ to $I$ and that it is 4, without any support.
METHOD 2
attempting to translate $\boldsymbol{M}$ to a graph or a list of cities polluted on each day
(M1)
correct graph or list
hence Isaacopolis is the last city to be polluted
A1
Note: Award M1A1A1 for a clear description of the graph in words leading to the correct answer.
[3 marks]
f.ii. it takes 4 days
A1
[1 mark]
f.iii.EITHER
the orders of the different vertices are:
E 2
F 1
G 2
H 2
I 1
T 2
(A1)
Note: Accept a list where each order is 2 greater than listed above.
OR
a correct diagram/graph showing the connections between the locations
(A1)
Note: Accept a diagram with loops at each vertex.
This mark should be awarded if candidate is clearly using their correct diagram from the previous part.
THEN
“Start at $F$ and end at I” OR “Start at I and end at F”
A1
Note: Award A1AO for “it could start at either F or I”.
Award A1A1 for “IGEHTF” OR “FTHEGI”.
Award $\mathbf{A 1 A 1}$ for ” $F$ and $I$ ” OR “I and $F$ “.
Question
This question compares possible designs for a new computer network between multiple school buildings, and whether they meet specific requirements.
A school’s administration team decides to install new fibre-optic internet cables underground. The school has eight buildings that need to be connected by these cables. A map of the school is shown below, with the internet access point of each building labelled A-H.
Jonas is planning where to install the underground cables. He begins by determining the distances, in metres, between the underground access points in each of the buildings.
He finds $\mathrm{AD}=89.2 \mathrm{~m}, \mathrm{DF}=104.9 \mathrm{~m}$ and $\mathrm{ADF}=83^{\circ}$.
The cost for installing the cable directly between A and F is $\$ 21310$.
Jonas estimates that it will cost $\$ 110$ per metre to install the cables between all the other buildings.
Jonas creates the following graph, $S$, using the cost of installing the cables between two buildings as the weight of each edge.
The computer network could be designed such that each building is directly connected to at least one other building and hence all buildings are indirectly connected.
The computer network fails if any part of it becomes unreachable from any other part. To help protect the network from failing, every building could be connected to at least two other buildings. In this way if one connection breaks, the building is still part of the computer network. Jonas can achieve this by finding a Hamiltonian cycle within the graph.
After more research, Jonas decides to install the cables as shown in the diagram below.
Each individual cable is installed such that each end of the cable is connected to a building’s access point. The connection between each end of a cable and an access point has a $1.4 \%$ probability of failing after a power surge.
For the network to be successful, each building in the network must be able to communicate with every other building in the network. In other words there must be a path that connects any two buildings in the network. Jonas would like the network to have less than a $2 \%$ probability of failing to operate after a power surge.
a. Find $\mathrm{AF}$.
b. Find the cost per metre of installing this cable.
c. State why the cost for installing the cable between A and F would be higher than between the other buildings.
d.i.By using Kruskal’s algorithm, find the minimum spanning tree for $S$, showing clearly the order in which edges are added.
d.iiHence find the minimum installation cost for the cables that would allow all the buildings to be part of the computer network.
e. State why a path that forms a Hamiltonian cycle does not always form an Eulerian circuit.
f. Starting at $\mathrm{D}$, use the nearest neighbour algorithm to find the upper bound for the installation cost of a computer network in the form of a Hamiltonian cycle.
Note: Although the graph is not complete, in this instance it is not necessary to form a table of least distances.
g. By deleting D, use the deleted vertex algorithm to find the lower bound for the installation cost of the cycle.
h. Show that Jonas’s network satisfies the requirement of there being less than a $2 \%$ probability of the network failing after a power surge.
▶️Answer/Explanation
a. $\mathrm{AF}^2=89.2^2+104.9^2-2(89.2)(104.9) \cos 83$
(M1)(A1)
Note: Award (M1) for substitution into the cosine rule and (A1) for correct substitution.
$$
\mathrm{AF}=129 \mathrm{~m}(129.150 \ldots)
$$
A1
[3 marks]
b. $21310 \div 129.150 \ldots$
(M1)
$\$ 165$
A1
[2 marks]
c. any reasonable statement referring to the lake
R1
(eg. there is a lake between A and F, the cables would need to be installed under/over/around the lake, special waterproof cables are needed for lake, etc.)
[1 mark]
d.i.edges (or weights) are chosen in the order
CE (8239)
DG (8668)
BD (8778)
AB (8811)
DE (8833)
EH (9251)
DF (11 539)
d.iiFinding the sum of the weights of their edges
(M1)
$$
\begin{aligned}
& 8239+8668+8778+8811+8833+9251+11539 \\
& \text { total cost }=\$ 64119 \quad \text { A1 }
\end{aligned}
$$
A1
[2 marks]
e. a Hamiltonian cycle is not always an Eulerian circuit as it does not have to include all edges of the graph (only all vertices)
R1
[1 mark]
f. edges (or weights) are chosen in the order
DG (8668)
GH (9603)
HE (9251)
EC (8239)
CB (13 156)
BA (8811)
AF (21 310)
FD (11 539)
finding the sum of the weights of their edges
(M1)
$8668+9603+9251+8239+13156+8811+21310+11539$
upper bound $=\$ 90577$
A1
[5 marks]
g. attempt to find MST after deleting vertex D
(M1)
these edges (or weights) (in any order)
CE (8239)
$\mathrm{AB}$ (8811)
EH (9251)
GH (9603)
BE (10 153)
FG (12 606)
A1
Note: Prim’s or Kruskal’s algorithm could be used at this stage.
reconnect D to MST with two different edges
(M1)
DG (8668)
BD (8778)
A1
Note: This $\boldsymbol{A 1}$ is independent of the first $\boldsymbol{A}$ mark and can be awarded if both DG and BD are chosen to reconnect D to the MST, even if the MST is incorrect.
finding the sum of the weights of their edges
(M1)
$$
8239+8811+9251+9603+10153+12606+8668+8778
$$
Note: For candidates with an incorrect MST or no MST, the weights of at least seven of the edges being summed (two of which must connect to D) must be shown to award this (M1).
lower bound $=\$ 76109$
A1
[6 marks]
h. METHOD 1
recognition of a binomial distribution
(M1)
$X \sim \mathrm{B}(2,0.014)$
finding the probability that a cable fails (at least one of its connections fails)
$\mathrm{P}(X>0)=0.027804$ OR $1-\mathrm{P}(X=0)=0.027804$
A1
recognition that two cables must fail for the network to go offline M1
recognition of binomial distribution for network, $Y \sim \mathrm{B}(8,0.027804)$
(M1)
A1
therefore, the diagram satisfies the requirement since $1.94 \%<2 \%$
AG
Note: Evidence of binomial distribution may be seen as combinations.
METHOD 2
recognition of a binomial distribution
(M1)
$X \sim \mathrm{B}(16,0.014)$
finding the probability that at least two connections fail
$\mathrm{P}(X \geq 2)=0.0206473 \ldots$ OR $\mathbf{1}-\mathbf{P}(\boldsymbol{X}<\mathbf{2})=\mathbf{0 . 0 2 0 6 4 7 3} \ldots$
A1
recognition that the previous answer is an overestimate
M1
finding probability of two ends of the same cable failing, $F \sim \mathrm{B}(2,0.014)$,
and the ends of the other 14 cables not failing, $S \sim \mathrm{B}(14,0.014)$
$\mathrm{P}(F=2) \times \mathrm{P}(S=0)=0.0000160891 \ldots$
(A1)
$0.0000160891 \ldots \times 8=0.00128713 \ldots$
$0.0206473 \ldots-0.00128713 \ldots=0.0194(0.0193602 \ldots)$
$0.0000160891 \ldots \times 8=0.00128713 \ldots$
$0.0206473 \ldots-0.00128713 \ldots=0.0194(0.0193602 \ldots)$
A1
therefore, the diagram satisfies the requirement since $1.94 \%<2 \%$
AG
METHOD 3
recognition of a binomial distribution $\quad M 1$ $X \sim \mathrm{B}(16,0.014)$
finding the probability that the network remains secure if 0 or 1 connections fail or if 2 connections fail provided that the second failed connection occurs at the other end of the cable with the first failure
(M1)
$\mathrm{P}($ remains secure $)=\mathrm{P}(X \leq 1)+\frac{1}{15} \times \mathrm{P}(X=2)$
A1
$$
=0.9806397625
$$
A1
$\mathrm{P}($ network fails $)=1-0.9806397625=0.0194(0.0193602 \ldots)$
A1
therefore, the diagram satisfies the requirement since $1.94 \%<2 \%$
AG
METHOD 4
P(network failing)
$=1-\mathrm{P}(0$ connections failing $)-\mathrm{P}(1$ connection failing $)-\mathrm{P}(2$ connections on the same cable failing $) \quad$ M1
$=1-0.986^{16}-C 1_{16} \times 0.014 \times 0.986^{15}-C 1_8 \times 0.014^2 \times 0.986^{14}$
A1A1A1
Note: Award $\mathbf{A 1}$ for each of $2^{\text {nd }}, 3^{\text {rd }}$ and last terms.
$=0.0194(0.0193602 \ldots)$
A1
therefore, the diagram satisfies the requirement since $1.94 \%<2 \%$
AG
[5 marks]
Question
$G$ is a simple, connected graph with eight vertices.
$H$ is a connected, planar graph, with $v$ vertices, $e$ edges and $f$ faces. Every face in $H$ is bounded by exactly $k$ edges.
a.i. Write down the minimum number of edges in $G$.
a.ii.Find the maximum number of edges in $G$.
a.iiiFind the maximum number of edges in $G$, given that $G$ contains an Eulerian circuit.
b.i.Explain why $2 e=k f$.
b.iiFind the value of $f$ when $v=9$ and $k=3$.
b.iiiFind the possible values of $f$ when $v=13$.
▶️Answer/Explanation
a.i. 7 (a tree)
A1
[1 mark]
a.ii. $\frac{8 \times 7}{2}(7+6+5+4+3+2+1)$ (a complete graph) (M1)
$$
=28
$$
A1
[2 marks]
a.iii $\frac{8 \times 6}{2}$ (since every vertex must be of degree 6) (M1)
$$
=24
$$
A1
[2 marks]
b.i.counting the edges around every face gives $k f$ edges
A1
but as every edge is counted in 2 faces $\quad \boldsymbol{R 1}$
$$
\Rightarrow k f=2 e \quad A G
$$
[2 marks]
b.ii.using $v-e+f=2$ with $v=9 \quad M 1$
EITHER
substituting $2 e=3 f$ into $2(9)-2 e+2 f=4 \quad$ (M1)
OR
substituting $e=\frac{3 f}{2}$ into $9-e+f=2 \quad$ (M1)
THEN
$$
18-f=4
$$
$f=14$
A1
b.iii $2 v-k f+2 f=4$ (or equivalent) M1
when $v=13$
$(k-2) f=22$ or $(2-k) f=-22$
A1
EITHER
$$
(k-2) f=1 \times 2 \times 11 \quad \text { M1 }
$$
OR
substituting at least two of $k=13,4,3$ into $f=\frac{22}{k-2}$ (or equivalent) M1
THEN
$f=2,11,22($ since $f>1) \quad$ A1
[4 marks]
Question
This question explores how graph algorithms can be applied to a graph with an unknown edge weight.
Graph $W$ is shown in the following diagram. The vertices of $W$ represent tourist attractions in a city. The weight of each edge represents the travel time, to the nearest minute, between two attractions. The route between A and F is currently being resurfaced and this has led to a variable travel time. For this reason, $\mathrm{AF}$ has an unknown travel time $x$ minutes, where $x \in \mathbb{Z}^{+}$.
Daniel plans to visit all the attractions, starting and finishing at A. He wants to minimize his travel time.
To find a lower bound for Daniel’s travel time, vertex A and its adjacent edges are first deleted.
Daniel makes a table to show the minimum travel time between each pair of attractions.
Write down the value of
To find an upper bound for Daniel’s travel time, the nearest neighbour algorithm is used, starting at vertex A.
Consider the case where $x=3$.
Consider the case where $x>3$.
a. Write down a Hamiltonian cycle in $W$.
b.i.Use Prim’s algorithm, starting at vertex B, to find the weight of the minimum spanning tree of the remaining graph. You should indicate clearly the order in which the algorithm selects each edge.
b.iiHence, for the case where $x<9$, find a lower bound for Daniel’s travel time, in terms of $x$.
c.i.p.
c.ii.q.
c.iiir.
d.i.Use the nearest neighbour algorithm to find two possible cycles.
d.iiFind the best upper bound for Daniel’s travel time.
e.i. Find the least value of $x$ for which the edge AF will definitely not be used by Daniel.
e.ii.Hence state the value of the upper bound for Daniel’s travel time for the value of $x$ found in part (e)(i).
f. The tourist office in the city has received complaints about the lack of cleanliness of some routes between the attractions. Corinne, the office manager, decides to inspect all the routes between all the attractions, starting and finishing at $\mathrm{H}$. The sum of the weights of all the edges in graph $W$ is $(92+x)$.
Corinne inspects all the routes as quickly as possible and takes 2 hours.
Find the value of $x$ during Corinne’s inspection.
▶️Answer/Explanation
a. e.g. $A B C D E G H F A$
A1
Note: Accept any other correct answers starting at any vertex.
[1 mark]
b.i. 7 vertices, so 6 edges required for MST
(M1)
Note: To award (M1), their 6 edges should not form a cycle.
Note: Award $\boldsymbol{M 1}$ for the first three edges in correct order, $\boldsymbol{A 1}$ for BH in correct order and $\mathbf{A 1}$ for all of the edges correct.
weight of MST $=33$
A1
Note: The final $\boldsymbol{A 1}$ can be awarded independently of previous marks.
[5 marks]
b.ii.Jower bound $=33+3+x$
(M1)
$$
=36+x
$$
A1
[2 marks]
c.i. $p=13$
A1
[1 mark]
c.ii. $q=17$
A1
[1 mark]
c.iiir $=14$
A1
[1 mark]
d.i.attempt to use nearest neighbour algorithm
any two correct cycles from
ABCDEGHFA, AFGHBCDE(F)A, AB(A)FGHCDE(F)A
(M1)
A1A1
Note: Bracketed vertices may be omitted in candidate’s answer.
Award M1AOA1 for candidates who list two correct sequences of vertices, but omit the final vertex A.
[3 marks]
d.ii.use ABCDEGHFA OR their shortest cycle from (d)(i)
(M1)
upper bound $=43$
A1
[2 marks]
e.i. cycle starts: ABCDEGHF
return to A has two options, $\mathrm{FA}=18$ or $x$
(M1)
hence least value of $x=19$
A1
[2 marks]
e.ii.upper bound $=58 \quad$ A2
[2 marks]
f. recognition that edges will be repeated / there are odd vertices
(M1)
$$
\mathrm{BH}+\mathrm{DG}=21, \mathrm{BD}+\mathrm{GH}=15, \mathrm{BG}+\mathrm{DH}=21 \text { OR } 18+x
$$
recognizing $\mathrm{BD}$ and $\mathrm{GH}$ is lowest weight and is repeated
(M1)
solution to CPP $=107+x$
A1
$x=13$
A1
Note: Award M1AOMOA1A1 if only pairing BD and GH is considered, leading to a correct answer.
[5 marks]