2025 OCR A Level Further Mathematics A Y544/01 Discrete Mathematics
Combined Question Paper & Final Marking Scheme
Oxford Cambridge and RSA
Wednesday 18 June 2025 – Afternoon
A Level Further Mathematics A
Y544/01 Discrete Mathematics
Time allowed: 1 hour 30 minutes
You must have:
• the Printed Answer Booklet
• the Formulae Booklet for A Level Further
QP
Mathematics A
• a scientific or graphical calculator
INSTRUCTIONS
• Use black ink. You can use an HB pencil, but only for graphs and diagrams.
• Write your answer to each question in the space provided in the Printed Answer
Booklet. If you need extra space use the lined pages at the end of the Printed Answer
Booklet. The question numbers must be clearly shown.
• Fill in the boxes on the front of the Printed Answer Booklet.
• Answer all the questions.
• Where appropriate, your answer should be supported with working. Marks might be
given for using a correct method, even if your answer is wrong.
• Give non-exact numerical answers correct to 3 significant figures unless a different
degree of accuracy is specified in the question.
• The acceleration due to gravity is denoted by g m s–2. When a numerical value is
needed use g = 9.8 unless a different value is specified in the question.
• Do not send this Question Paper for marking. Keep it in the centre or recycle it.
INFORMATION
• The total mark for this paper is 75.
• The marks for each question are shown in brackets [ ].
• This document has 8 pages.
ADVICE
• Read each question carefully before you start your answer.
, © OCR 2025 [Y/508/5513] OCR is an exempt Charity
DC (PQ/FC) 359474/3 Turn over
*1920756440*
, 2
1 A coach operator offers sightseeing tours of a city. The sightseeing tour starts and ends at stop A,
and there are tourist attractions at B, C, D, E, F and G. The table below shows the distances in
metres that the coach must travel between each of the seven stops.
A B C D E F G
A – 120 100 230 260 150 200
B 120 – 180 210 200 250 280
C 100 180 – 235 190 170 270
D 230 210 235 – 170 185 210
E 260 200 190 170 – 210 270
F 150 250 170 185 210 – 195
G 200 280 270 210 270 195 –
The coach operator wants to find a route which starts and ends at A, visiting every tourist
attraction once.
(a) State the standard network problem that they must solve. [1]
(b) Use the nearest neighbour method to find an upper bound for the length of the coach
operator’s route starting at A. [2]
(c) Beginning by removing stop A to reduce the network, use an algorithm to determine a lower
bound for the length of the coach operator’s route. [4]
(d) By referring to your lower bound, comment on the length of the route found by the nearest
neighbour method. [1]
© OCR 2025 Y544/01 Jun25
, 3
2 (a) Graph G is shown below
A B
C
F
E D
(i) Show that graph G is not bipartite. [2]
(ii) Use Kuratowski’s Theorem to show that graph G is not planar. [3]
(iii) Determine whether graph G is simply connected. [1]
(b) The adjacency matrix for a digraph H is shown below
To
J K L M N O
J 0 1 1 0 1 0
K 2 0 1 1 0 0
L 1 1 0 1 1 1
From
M 0 0 1 1 0 1
N 1 0 1 0 0 1
O 0 1 0 1 1 0
(i) Write down the indegree and outdegree of node L. [2]
(ii) Determine whether digraph H is simply connected. [1]
© OCR 2025 Y544/01 Jun25 Turn over
Combined Question Paper & Final Marking Scheme
Oxford Cambridge and RSA
Wednesday 18 June 2025 – Afternoon
A Level Further Mathematics A
Y544/01 Discrete Mathematics
Time allowed: 1 hour 30 minutes
You must have:
• the Printed Answer Booklet
• the Formulae Booklet for A Level Further
QP
Mathematics A
• a scientific or graphical calculator
INSTRUCTIONS
• Use black ink. You can use an HB pencil, but only for graphs and diagrams.
• Write your answer to each question in the space provided in the Printed Answer
Booklet. If you need extra space use the lined pages at the end of the Printed Answer
Booklet. The question numbers must be clearly shown.
• Fill in the boxes on the front of the Printed Answer Booklet.
• Answer all the questions.
• Where appropriate, your answer should be supported with working. Marks might be
given for using a correct method, even if your answer is wrong.
• Give non-exact numerical answers correct to 3 significant figures unless a different
degree of accuracy is specified in the question.
• The acceleration due to gravity is denoted by g m s–2. When a numerical value is
needed use g = 9.8 unless a different value is specified in the question.
• Do not send this Question Paper for marking. Keep it in the centre or recycle it.
INFORMATION
• The total mark for this paper is 75.
• The marks for each question are shown in brackets [ ].
• This document has 8 pages.
ADVICE
• Read each question carefully before you start your answer.
, © OCR 2025 [Y/508/5513] OCR is an exempt Charity
DC (PQ/FC) 359474/3 Turn over
*1920756440*
, 2
1 A coach operator offers sightseeing tours of a city. The sightseeing tour starts and ends at stop A,
and there are tourist attractions at B, C, D, E, F and G. The table below shows the distances in
metres that the coach must travel between each of the seven stops.
A B C D E F G
A – 120 100 230 260 150 200
B 120 – 180 210 200 250 280
C 100 180 – 235 190 170 270
D 230 210 235 – 170 185 210
E 260 200 190 170 – 210 270
F 150 250 170 185 210 – 195
G 200 280 270 210 270 195 –
The coach operator wants to find a route which starts and ends at A, visiting every tourist
attraction once.
(a) State the standard network problem that they must solve. [1]
(b) Use the nearest neighbour method to find an upper bound for the length of the coach
operator’s route starting at A. [2]
(c) Beginning by removing stop A to reduce the network, use an algorithm to determine a lower
bound for the length of the coach operator’s route. [4]
(d) By referring to your lower bound, comment on the length of the route found by the nearest
neighbour method. [1]
© OCR 2025 Y544/01 Jun25
, 3
2 (a) Graph G is shown below
A B
C
F
E D
(i) Show that graph G is not bipartite. [2]
(ii) Use Kuratowski’s Theorem to show that graph G is not planar. [3]
(iii) Determine whether graph G is simply connected. [1]
(b) The adjacency matrix for a digraph H is shown below
To
J K L M N O
J 0 1 1 0 1 0
K 2 0 1 1 0 0
L 1 1 0 1 1 1
From
M 0 0 1 1 0 1
N 1 0 1 0 0 1
O 0 1 0 1 1 0
(i) Write down the indegree and outdegree of node L. [2]
(ii) Determine whether digraph H is simply connected. [1]
© OCR 2025 Y544/01 Jun25 Turn over
