SubjectScout
ENAR
Sign inGet started
← Back to interactive practice
Print questions only
IB · MATH AI HL

Mathematics: Applications & Interpretation HL

Graph theory and networks — Topic 3 HL

Name: ____________________Date: October 2, 2026
  1. 1.

    A simple graph has vertices with degrees 3, 2, 2, 3, 2. Use the handshaking lemma to find the number of edges in the graph.

    [2 marks]

    Marking points

    • States the handshaking lemma: the sum of all vertex degrees equals twice the number of edges.
    • Calculates the sum of degrees as 3+2+2+3+2 = 12, and divides by 2 to obtain 6 edges.

    Examiner tip: The handshaking lemma also tells you the sum of degrees in any graph must always be even — a quick way to check whether a proposed degree sequence is even possible.

  2. 2.

    Marking analysis: A learner attempts the following task: “A simple graph has vertices with degrees 3, 2, 2, 3, 2. Use the handshaking lemma to find the number of edges in the graph.” Their response addresses only this point: “States the handshaking lemma: the sum of all vertex degrees equals twice the number of edges.” Evaluate the response against the complete 2-mark task. Identify what earns credit and state every additional requirement needed for full marks.

    [2 marks]

    Marking points

    • Recognises credit for the stated point: States the handshaking lemma: the sum of all vertex degrees equals twice the number of edges.
    • Identifies the missing requirement: Calculates the sum of degrees as 3+2+2+3+2 = 12, and divides by 2 to obtain 6 edges.

    Examiner tip: Treat each marking point as a separate requirement. Do not award the same idea twice, and do not infer work the learner did not show.

  3. 3.

    Explain why no simple graph can have the degree sequence 3, 2, 2, 2.

    [2 marks] · no calculator

    Marking points

    • Calculates the sum of the proposed degrees: 3 + 2 + 2 + 2 = 9.
    • States that this sum is odd, which contradicts the handshaking lemma (the sum of degrees must be even), so no such graph exists.

    Examiner tip: Checking whether the sum of a proposed degree sequence is even is always the fastest first check for realisability — an odd sum rules it out immediately, with no need for further analysis.

  4. 4.

    Marking analysis: A learner attempts the following task: “Explain why no simple graph can have the degree sequence 3, 2, 2, 2.” Their response addresses only this point: “Calculates the sum of the proposed degrees: 3 + 2 + 2 + 2 = 9.” Evaluate the response against the complete 2-mark task. Identify what earns credit and state every additional requirement needed for full marks.

    [2 marks] · no calculator

    Marking points

    • Recognises credit for the stated point: Calculates the sum of the proposed degrees: 3 + 2 + 2 + 2 = 9.
    • Identifies the missing requirement: States that this sum is odd, which contradicts the handshaking lemma (the sum of degrees must be even), so no such graph exists.

    Examiner tip: Treat each marking point as a separate requirement. Do not award the same idea twice, and do not infer work the learner did not show.

  5. 5.

    A graph has vertices A, B, C, D and edges AB, AC, BC, BD. Construct the adjacency matrix for this graph, and verify that the sum of each row equals the degree of the corresponding vertex.

    [4 marks]

    Marking points

    • Constructs the 4×4 adjacency matrix with rows/columns ordered A, B, C, D: [[0,1,1,0],[1,0,1,1],[1,1,0,0],[0,1,0,0]].
    • Sums row A: 0+1+1+0 = 2, matching the degree of A (connected to B and C).
    • Sums row B: 1+0+1+1 = 3, matching the degree of B (connected to A, C, D).
    • Sums rows C and D similarly, confirming degrees 2 and 1 respectively.

    Examiner tip: In an adjacency matrix for a simple undirected graph, the matrix is always symmetric and every diagonal entry is zero, since a vertex is never adjacent to itself.

  6. 6.

    Marking analysis: A learner attempts the following task: “A graph has vertices A, B, C, D and edges AB, AC, BC, BD. Construct the adjacency matrix for this graph, and verify that the sum of each row equals the degree of the corresponding vertex.” Their response addresses only this point: “Constructs the 4×4 adjacency matrix with rows/columns ordered A, B, C, D: [[0,1,1,0],[1,0,1,1],[1,1,0,0],[0,1,0,0]].” Evaluate the response against the complete 4-mark task. Identify what earns credit and state every additional requirement needed for full marks.

    [4 marks]

    Marking points

    • Recognises credit for the stated point: Constructs the 4×4 adjacency matrix with rows/columns ordered A, B, C, D: [[0,1,1,0],[1,0,1,1],[1,1,0,0],[0,1,0,0]].
    • Identifies the missing requirement: Sums row A: 0+1+1+0 = 2, matching the degree of A (connected to B and C).
    • Identifies the missing requirement: Sums row B: 1+0+1+1 = 3, matching the degree of B (connected to A, C, D).
    • Identifies the missing requirement: Sums rows C and D similarly, confirming degrees 2 and 1 respectively.

    Examiner tip: Treat each marking point as a separate requirement. Do not award the same idea twice, and do not infer work the learner did not show.

  7. 7.

    A network connecting six towns A, B, C, D, E, F has the following roads and distances (km): AB=4, AC=2, BC=1, BD=5, CD=8, CE=10, DE=2, DF=6, EF=3. Use Kruskal's algorithm to find a minimum spanning tree for this network, showing the order in which edges are added, and state its total weight.

    [6 marks]

    Marking points

    • Sorts the edges by increasing weight: BC(1), AC(2), DE(2), EF(3), AB(4), BD(5), DF(6), CD(8), CE(10).
    • Adds BC(1): no cycle formed.
    • Adds AC(2): no cycle formed.
    • Adds DE(2): no cycle formed.
    • Adds EF(3): no cycle formed; rejects AB(4) since A and B are already connected via C; adds BD(5): no cycle formed, connecting all six vertices with five edges.
    • States the minimum spanning tree edges {BC, AC, DE, EF, BD} with total weight 1+2+2+3+5 = 13.

    Examiner tip: Kruskal's algorithm always considers edges in increasing order of weight and rejects any edge that would create a cycle — a running tally of which vertices are already connected (for example, using a sketch) makes this easy to check.

  8. 8.

    Marking analysis: A learner attempts the following task: “A network connecting six towns A, B, C, D, E, F has the following roads and distances (km): AB=4, AC=2, BC=1, BD=5, CD=8, CE=10, DE=2, DF=6, EF=3. Use Kruskal's algorithm to find a minimum spanning tree for this network, showing the order in which edges are added, and state its total weight.” Their response addresses only this point: “Sorts the edges by increasing weight: BC(1), AC(2), DE(2), EF(3), AB(4), BD(5), DF(6), CD(8), CE(10).” Evaluate the response against the complete 6-mark task. Identify what earns credit and state every additional requirement needed for full marks.

    [6 marks]

    Marking points

    • Recognises credit for the stated point: Sorts the edges by increasing weight: BC(1), AC(2), DE(2), EF(3), AB(4), BD(5), DF(6), CD(8), CE(10).
    • Identifies the missing requirement: Adds BC(1): no cycle formed.
    • Identifies the missing requirement: Adds AC(2): no cycle formed.
    • Identifies the missing requirement: Adds DE(2): no cycle formed.
    • Identifies the missing requirement: Adds EF(3): no cycle formed; rejects AB(4) since A and B are already connected via C; adds BD(5): no cycle formed, connecting all six vertices with five edges.
    • Identifies the missing requirement: States the minimum spanning tree edges {BC, AC, DE, EF, BD} with total weight 1+2+2+3+5 = 13.

    Examiner tip: Treat each marking point as a separate requirement. Do not award the same idea twice, and do not infer work the learner did not show.

  9. 9.

    Using the same network as the previous question, apply Prim's algorithm starting from vertex A to find a minimum spanning tree, showing the order in which vertices are added. Confirm that the total weight matches the result from Kruskal's algorithm.

    [6 marks]

    Marking points

    • Starts at A; the cheapest edge from the tree {A} is AC(2), so C is added.
    • The cheapest edge from {A, C} to an outside vertex is BC(1), so B is added.
    • The cheapest edge from {A, B, C} to an outside vertex is BD(5) (AB(4) is rejected as it connects two vertices already in the tree); adds D.
    • The cheapest edge from the current tree to an outside vertex is DE(2), so E is added, then EF(3), so F is added.
    • Lists the selected edges as {AC, BC, BD, DE, EF}.
    • Confirms the total weight 2+1+5+2+3 = 13, matching Kruskal's result.

    Examiner tip: Prim's algorithm grows a single connected tree outward from the starting vertex, unlike Kruskal's algorithm which can add disconnected edges before they eventually join up — both always produce a minimum spanning tree of the same total weight.

  10. 10.

    Marking analysis: A learner attempts the following task: “Using the same network as the previous question, apply Prim's algorithm starting from vertex A to find a minimum spanning tree, showing the order in which vertices are added. Confirm that the total weight matches the result from Kruskal's algorithm.” Their response addresses only this point: “Starts at A; the cheapest edge from the tree {A} is AC(2), so C is added.” Evaluate the response against the complete 6-mark task. Identify what earns credit and state every additional requirement needed for full marks.

    [6 marks]

    Marking points

    • Recognises credit for the stated point: Starts at A; the cheapest edge from the tree {A} is AC(2), so C is added.
    • Identifies the missing requirement: The cheapest edge from {A, C} to an outside vertex is BC(1), so B is added.
    • Identifies the missing requirement: The cheapest edge from {A, B, C} to an outside vertex is BD(5) (AB(4) is rejected as it connects two vertices already in the tree); adds D.
    • Identifies the missing requirement: The cheapest edge from the current tree to an outside vertex is DE(2), so E is added, then EF(3), so F is added.
    • Identifies the missing requirement: Lists the selected edges as {AC, BC, BD, DE, EF}.
    • Identifies the missing requirement: Confirms the total weight 2+1+5+2+3 = 13, matching Kruskal's result.

    Examiner tip: Treat each marking point as a separate requirement. Do not award the same idea twice, and do not infer work the learner did not show.

  11. 11.

    A network has vertices P, Q, R, S, T, U with weighted edges: PQ=7, PR=9, PU=14, QR=10, QS=15, RS=11, RU=2, ST=6, UT=9. Use Dijkstra's algorithm to find the shortest path from P to T, stating the path and its total length.

    [7 marks]

    Marking points

    • Assigns P a permanent label of 0 and considers its neighbours: Q gets a working value of 7, R gets 9, U gets 14.
    • Gives Q the next permanent label (7), the smallest working value.
    • Gives R the next permanent label (9); updates U's working value via R: 9+2=11, which improves on 14.
    • Gives U the next permanent label (11); updates S via R (9+11=20) and via Q (7+15=22), keeping the smaller value 20.
    • Gives S a permanent label of 20; updates T via U (11+9=20) and via S (20+6=26), keeping the smaller value 20.
    • Gives T a permanent label of 20, and backtracks the predecessors to find the path P → R → U → T.
    • States the shortest path as P → R → U → T with total length 20.

    Examiner tip: Dijkstra's algorithm always permanently labels the vertex with the smallest working value at each stage — once a vertex is permanently labelled, its shortest distance from the start can never improve further.

  12. 12.

    Marking analysis: A learner attempts the following task: “A network has vertices P, Q, R, S, T, U with weighted edges: PQ=7, PR=9, PU=14, QR=10, QS=15, RS=11, RU=2, ST=6, UT=9. Use Dijkstra's algorithm to find the shortest path from P to T, stating the path and its total length.” Their response addresses only this point: “Assigns P a permanent label of 0 and considers its neighbours: Q gets a working value of 7, R gets 9, U gets 14.” Evaluate the response against the complete 7-mark task. Identify what earns credit and state every additional requirement needed for full marks.

    [7 marks]

    Marking points

    • Recognises credit for the stated point: Assigns P a permanent label of 0 and considers its neighbours: Q gets a working value of 7, R gets 9, U gets 14.
    • Identifies the missing requirement: Gives Q the next permanent label (7), the smallest working value.
    • Identifies the missing requirement: Gives R the next permanent label (9); updates U's working value via R: 9+2=11, which improves on 14.
    • Identifies the missing requirement: Gives U the next permanent label (11); updates S via R (9+11=20) and via Q (7+15=22), keeping the smaller value 20.
    • Identifies the missing requirement: Gives S a permanent label of 20; updates T via U (11+9=20) and via S (20+6=26), keeping the smaller value 20.
    • Identifies the missing requirement: Gives T a permanent label of 20, and backtracks the predecessors to find the path P → R → U → T.
    • Identifies the missing requirement: States the shortest path as P → R → U → T with total length 20.

    Examiner tip: Treat each marking point as a separate requirement. Do not award the same idea twice, and do not infer work the learner did not show.

  13. 13.

    Using the same Dijkstra's algorithm table from the previous question, state the order in which the vertices P, Q, R, S, T, U received their permanent labels.

    [2 marks]

    Marking points

    • States the order of permanent labelling as P, Q, R, U, S, T.
    • Notes that S and T both receive a final permanent label of 20, but S is labelled first since it was reached via a smaller working value before T's was finalised.

    Examiner tip: Two vertices can legitimately end up with the same final shortest distance from the source — this does not indicate an error, it simply means two different paths happen to have equal total length.

  14. 14.

    Marking analysis: A learner attempts the following task: “Using the same Dijkstra's algorithm table from the previous question, state the order in which the vertices P, Q, R, S, T, U received their permanent labels.” Their response addresses only this point: “States the order of permanent labelling as P, Q, R, U, S, T.” Evaluate the response against the complete 2-mark task. Identify what earns credit and state every additional requirement needed for full marks.

    [2 marks]

    Marking points

    • Recognises credit for the stated point: States the order of permanent labelling as P, Q, R, U, S, T.
    • Identifies the missing requirement: Notes that S and T both receive a final permanent label of 20, but S is labelled first since it was reached via a smaller working value before T's was finalised.

    Examiner tip: Treat each marking point as a separate requirement. Do not award the same idea twice, and do not infer work the learner did not show.

  15. 15.

    Five cities W, X, Y, Z, V have the following direct distances (km): WX=12, WY=10, WZ=19, WV=8, XY=3, XZ=7, XV=6, YZ=2, YV=20, ZV=4. Starting at W, use the nearest-neighbour algorithm to find an upper bound for the length of a travelling salesman tour that visits every city once and returns to W.

    [5 marks]

    Marking points

    • From W, the nearest unvisited city is V (8 km).
    • From V, the nearest unvisited city is Z (4 km).
    • From Z, the nearest unvisited city is Y (2 km).
    • From Y, the nearest unvisited city is X (3 km); returns to W from X (12 km).
    • States the route W→V→Z→Y→X→W with total upper bound 8+4+2+3+12 = 29 km.

    Examiner tip: The nearest-neighbour algorithm always makes the locally best choice at each step, so it is fast and simple, but it does not guarantee the globally shortest possible tour — it only provides an upper bound.

  16. 16.

    Marking analysis: A learner attempts the following task: “Five cities W, X, Y, Z, V have the following direct distances (km): WX=12, WY=10, WZ=19, WV=8, XY=3, XZ=7, XV=6, YZ=2, YV=20, ZV=4. Starting at W, use the nearest-neighbour algorithm to find an upper bound for the length of a travelling salesman tour that visits every city once and returns to W.” Their response addresses only this point: “From W, the nearest unvisited city is V (8 km).” Evaluate the response against the complete 5-mark task. Identify what earns credit and state every additional requirement needed for full marks.

    [5 marks]

    Marking points

    • Recognises credit for the stated point: From W, the nearest unvisited city is V (8 km).
    • Identifies the missing requirement: From V, the nearest unvisited city is Z (4 km).
    • Identifies the missing requirement: From Z, the nearest unvisited city is Y (2 km).
    • Identifies the missing requirement: From Y, the nearest unvisited city is X (3 km); returns to W from X (12 km).
    • Identifies the missing requirement: States the route W→V→Z→Y→X→W with total upper bound 8+4+2+3+12 = 29 km.

    Examiner tip: Treat each marking point as a separate requirement. Do not award the same idea twice, and do not infer work the learner did not show.

  17. 17.

    Using the same five cities as the previous question, find a lower bound for the travelling salesman tour by deleting city W, finding the minimum spanning tree of the remaining four cities, and adding the two shortest edges connected to W.

    [6 marks]

    Marking points

    • Deletes W and finds the minimum spanning tree of X, Y, Z, V using Kruskal's or Prim's algorithm.
    • Obtains the minimum spanning tree edges {YZ(2), XY(3), ZV(4)} with total weight 9.
    • Identifies the two shortest edges connected to W as WV(8) and WY(10).
    • Adds these to the minimum spanning tree weight: 9 + 8 + 10 = 27.
    • States the lower bound as 27 km.
    • Concludes that the optimal tour length lies between the lower bound 27 km and the upper bound 29 km found previously.

    Examiner tip: Combining the deleted-vertex lower bound with the nearest-neighbour upper bound sandwiches the true optimal tour length between two values, even when finding the exact optimal tour by brute force would be impractical.

  18. 18.

    Marking analysis: A learner attempts the following task: “Using the same five cities as the previous question, find a lower bound for the travelling salesman tour by deleting city W, finding the minimum spanning tree of the remaining four cities, and adding the two shortest edges connected to W.” Their response addresses only this point: “Deletes W and finds the minimum spanning tree of X, Y, Z, V using Kruskal's or Prim's algorithm.” Evaluate the response against the complete 6-mark task. Identify what earns credit and state every additional requirement needed for full marks.

    [6 marks]

    Marking points

    • Recognises credit for the stated point: Deletes W and finds the minimum spanning tree of X, Y, Z, V using Kruskal's or Prim's algorithm.
    • Identifies the missing requirement: Obtains the minimum spanning tree edges {YZ(2), XY(3), ZV(4)} with total weight 9.
    • Identifies the missing requirement: Identifies the two shortest edges connected to W as WV(8) and WY(10).
    • Identifies the missing requirement: Adds these to the minimum spanning tree weight: 9 + 8 + 10 = 27.
    • Identifies the missing requirement: States the lower bound as 27 km.
    • Identifies the missing requirement: Concludes that the optimal tour length lies between the lower bound 27 km and the upper bound 29 km found previously.

    Examiner tip: Treat each marking point as a separate requirement. Do not award the same idea twice, and do not infer work the learner did not show.

  19. 19.

    A delivery network forms a graph where every edge must be traversed at least once, starting and ending at the depot. The edges and distances (km) are: AB=3, BC=4, CA=5, CD=6, where A is the depot. Exactly two vertices, C and D, have odd degree. Find the length of the shortest possible route that traverses every edge at least once and returns to A.

    [5 marks]

    Marking points

    • Calculates the total weight of all edges: 3 + 4 + 5 + 6 = 18.
    • Identifies the two odd-degree vertices as C and D (this is the Chinese postman problem).
    • Finds the shortest path between the two odd vertices C and D, which is the direct edge CD = 6.
    • Adds this shortest path weight to the total edge weight as the duplicated route: 18 + 6 = 24.
    • States the shortest route length as 24 km.

    Examiner tip: The Chinese postman problem always requires duplicating the shortest path between odd-degree vertices (in pairs) to make every vertex even, so an Euler circuit traversing every edge becomes possible.

  20. 20.

    Marking analysis: A learner attempts the following task: “A delivery network forms a graph where every edge must be traversed at least once, starting and ending at the depot. The edges and distances (km) are: AB=3, BC=4, CA=5, CD=6, where A is the depot. Exactly two vertices, C and D, have odd degree. Find the length of the shortest possible route that traverses every edge at least once and returns to A.” Their response addresses only this point: “Calculates the total weight of all edges: 3 + 4 + 5 + 6 = 18.” Evaluate the response against the complete 5-mark task. Identify what earns credit and state every additional requirement needed for full marks.

    [5 marks]

    Marking points

    • Recognises credit for the stated point: Calculates the total weight of all edges: 3 + 4 + 5 + 6 = 18.
    • Identifies the missing requirement: Identifies the two odd-degree vertices as C and D (this is the Chinese postman problem).
    • Identifies the missing requirement: Finds the shortest path between the two odd vertices C and D, which is the direct edge CD = 6.
    • Identifies the missing requirement: Adds this shortest path weight to the total edge weight as the duplicated route: 18 + 6 = 24.
    • Identifies the missing requirement: States the shortest route length as 24 km.

    Examiner tip: Treat each marking point as a separate requirement. Do not award the same idea twice, and do not infer work the learner did not show.

  21. 21.

    For each of the following degree sequences, state whether the corresponding graph has an Euler circuit, an Euler trail (but not a circuit), or neither: (a) 4, 4, 2, 2 (all even). (b) 3, 3, 2, 2 (exactly two odd). (c) 3, 3, 3, 3 (four odd).

    [3 marks] · no calculator

    Marking points

    • States that (a), with all vertices of even degree, has an Euler circuit.
    • States that (b), with exactly two vertices of odd degree, has an Euler trail but not a circuit (it must start and end at the two odd vertices).
    • States that (c), with four vertices of odd degree, has neither an Euler circuit nor an Euler trail.

    Examiner tip: Count the number of odd-degree vertices: zero means an Euler circuit exists, exactly two means only an Euler trail exists, and any other number (always even, by the handshaking lemma) means neither exists.

  22. 22.

    Marking analysis: A learner attempts the following task: “For each of the following degree sequences, state whether the corresponding graph has an Euler circuit, an Euler trail (but not a circuit), or neither: (a) 4, 4, 2, 2 (all even). (b) 3, 3, 2, 2 (exactly two odd). (c) 3, 3, 3, 3 (four odd).” Their response addresses only this point: “States that (a), with all vertices of even degree, has an Euler circuit.” Evaluate the response against the complete 3-mark task. Identify what earns credit and state every additional requirement needed for full marks.

    [3 marks] · no calculator

    Marking points

    • Recognises credit for the stated point: States that (a), with all vertices of even degree, has an Euler circuit.
    • Identifies the missing requirement: States that (b), with exactly two vertices of odd degree, has an Euler trail but not a circuit (it must start and end at the two odd vertices).
    • Identifies the missing requirement: States that (c), with four vertices of odd degree, has neither an Euler circuit nor an Euler trail.

    Examiner tip: Treat each marking point as a separate requirement. Do not award the same idea twice, and do not infer work the learner did not show.

  23. 23.

    Explain why a tree with n vertices always has exactly n − 1 edges, and state the number of edges in a tree with 6 vertices.

    [3 marks] · no calculator

    Marking points

    • Explains that a tree is a connected graph with no cycles, and that connecting n vertices with the fewest possible edges while remaining connected requires exactly n − 1 edges.
    • Notes that adding any further edge to a tree would necessarily create a cycle, while removing any edge would disconnect it.
    • States that a tree with 6 vertices has 6 − 1 = 5 edges.

    Examiner tip: A minimum spanning tree of a connected graph with n vertices always has exactly n − 1 edges — this is a quick way to check whether a proposed spanning tree is complete.

  24. 24.

    Marking analysis: A learner attempts the following task: “Explain why a tree with n vertices always has exactly n − 1 edges, and state the number of edges in a tree with 6 vertices.” Their response addresses only this point: “Explains that a tree is a connected graph with no cycles, and that connecting n vertices with the fewest possible edges while remaining connected requires exactly n − 1 edges.” Evaluate the response against the complete 3-mark task. Identify what earns credit and state every additional requirement needed for full marks.

    [3 marks] · no calculator

    Marking points

    • Recognises credit for the stated point: Explains that a tree is a connected graph with no cycles, and that connecting n vertices with the fewest possible edges while remaining connected requires exactly n − 1 edges.
    • Identifies the missing requirement: Notes that adding any further edge to a tree would necessarily create a cycle, while removing any edge would disconnect it.
    • Identifies the missing requirement: States that a tree with 6 vertices has 6 − 1 = 5 edges.

    Examiner tip: Treat each marking point as a separate requirement. Do not award the same idea twice, and do not infer work the learner did not show.

  25. 25.

    A triangle graph has vertices A, B, C, each pair joined by an edge, with adjacency matrix M = [[0,1,1],[1,0,1],[1,1,0]]. Calculate M², and explain what the entries of M² represent.

    [4 marks]

    Marking points

    • Multiplies M by itself to obtain M² = [[2,1,1],[1,2,1],[1,1,2]].
    • Explains that each off-diagonal entry (i, j) of M² gives the number of walks of length 2 from vertex i to vertex j.
    • Explains that each diagonal entry of M² equals the degree of that vertex, since it counts walks that leave and return via each of its edges.
    • Verifies that the diagonal entries (all 2) match the degree of each vertex in this triangle graph.

    Examiner tip: Powers of an adjacency matrix always count walks of that exact length between vertices, including walks that repeat edges or vertices — this is different from counting simple paths.

  26. 26.

    Marking analysis: A learner attempts the following task: “A triangle graph has vertices A, B, C, each pair joined by an edge, with adjacency matrix M = [[0,1,1],[1,0,1],[1,1,0]]. Calculate M², and explain what the entries of M² represent.” Their response addresses only this point: “Multiplies M by itself to obtain M² = [[2,1,1],[1,2,1],[1,1,2]].” Evaluate the response against the complete 4-mark task. Identify what earns credit and state every additional requirement needed for full marks.

    [4 marks]

    Marking points

    • Recognises credit for the stated point: Multiplies M by itself to obtain M² = [[2,1,1],[1,2,1],[1,1,2]].
    • Identifies the missing requirement: Explains that each off-diagonal entry (i, j) of M² gives the number of walks of length 2 from vertex i to vertex j.
    • Identifies the missing requirement: Explains that each diagonal entry of M² equals the degree of that vertex, since it counts walks that leave and return via each of its edges.
    • Identifies the missing requirement: Verifies that the diagonal entries (all 2) match the degree of each vertex in this triangle graph.

    Examiner tip: Treat each marking point as a separate requirement. Do not award the same idea twice, and do not infer work the learner did not show.

  27. 27.

    Define what is meant by a Hamiltonian cycle, and find one Hamiltonian cycle in the five-city network from an earlier question (W, X, Y, Z, V, all pairs connected), stating its total length.

    [3 marks]

    Marking points

    • Defines a Hamiltonian cycle as a closed route that visits every vertex of a graph exactly once before returning to the starting vertex.
    • States a valid Hamiltonian cycle, such as W→X→Y→Z→V→W.
    • Calculates its total length as 12 + 3 + 2 + 4 + 8 = 29 km, noting that any valid Hamiltonian cycle is acceptable, not necessarily the shortest.

    Examiner tip: A Hamiltonian cycle only needs to visit every vertex exactly once — it does not need to be the shortest possible such cycle unless the question specifically asks for the optimal tour.

  28. 28.

    Marking analysis: A learner attempts the following task: “Define what is meant by a Hamiltonian cycle, and find one Hamiltonian cycle in the five-city network from an earlier question (W, X, Y, Z, V, all pairs connected), stating its total length.” Their response addresses only this point: “Defines a Hamiltonian cycle as a closed route that visits every vertex of a graph exactly once before returning to the starting vertex.” Evaluate the response against the complete 3-mark task. Identify what earns credit and state every additional requirement needed for full marks.

    [3 marks]

    Marking points

    • Recognises credit for the stated point: Defines a Hamiltonian cycle as a closed route that visits every vertex of a graph exactly once before returning to the starting vertex.
    • Identifies the missing requirement: States a valid Hamiltonian cycle, such as W→X→Y→Z→V→W.
    • Identifies the missing requirement: Calculates its total length as 12 + 3 + 2 + 4 + 8 = 29 km, noting that any valid Hamiltonian cycle is acceptable, not necessarily the shortest.

    Examiner tip: Treat each marking point as a separate requirement. Do not award the same idea twice, and do not infer work the learner did not show.

  29. 29.

    Explain the key difference between a tree and a general connected graph, in terms of the number of edges relative to the number of vertices, and in terms of cycles.

    [2 marks] · no calculator

    Marking points

    • Explains that a tree is a connected graph with exactly n − 1 edges and no cycles, while a general connected graph may have n − 1 or more edges and can contain one or more cycles.
    • Notes that every tree is a connected graph, but not every connected graph is a tree.

    Examiner tip: Think of a tree as the 'minimal' way to keep a graph connected — any extra edge beyond n − 1 necessarily creates a cycle.

  30. 30.

    Marking analysis: A learner attempts the following task: “Explain the key difference between a tree and a general connected graph, in terms of the number of edges relative to the number of vertices, and in terms of cycles.” Their response addresses only this point: “Explains that a tree is a connected graph with exactly n − 1 edges and no cycles, while a general connected graph may have n − 1 or more edges and can contain one or more cycles.” Evaluate the response against the complete 2-mark task. Identify what earns credit and state every additional requirement needed for full marks.

    [2 marks] · no calculator

    Marking points

    • Recognises credit for the stated point: Explains that a tree is a connected graph with exactly n − 1 edges and no cycles, while a general connected graph may have n − 1 or more edges and can contain one or more cycles.
    • Identifies the missing requirement: Notes that every tree is a connected graph, but not every connected graph is a tree.

    Examiner tip: Treat each marking point as a separate requirement. Do not award the same idea twice, and do not infer work the learner did not show.

  31. 31.

    Five locations A, B, C, D, E form a square ABCD of side 1 km (with diagonals AC = BD ≈ 1.41 km), plus a fifth location E that is 6.02 km from A and D, and 5.02 km from B and C. Starting at A, the nearest-neighbour algorithm gives the tour A→B→C→D→E→A with length 15.04 km, but the optimal tour A→B→E→C→D→A has length 13.04 km. Explain why the nearest-neighbour algorithm failed to find the optimal tour in this case.

    [3 marks] · no calculator

    Marking points

    • Explains that the nearest-neighbour algorithm makes the locally optimal choice at each step without considering the overall structure of the remaining route.
    • Explains that by visiting C and D before the distant point E, the algorithm is forced to make two long journeys to and from E (D to E and E back to A), rather than visiting E in a single efficient detour from B.
    • Concludes that greedy, locally-optimal choices do not always lead to a globally optimal solution for the travelling salesman problem.

    Examiner tip: The nearest-neighbour algorithm is a heuristic, not an exact method — it is fast but offers no guarantee of optimality, which is why it is always paired with a lower bound to assess how far from optimal it might be.

  32. 32.

    Marking analysis: A learner attempts the following task: “Five locations A, B, C, D, E form a square ABCD of side 1 km (with diagonals AC = BD ≈ 1.41 km), plus a fifth location E that is 6.02 km from A and D, and 5.02 km from B and C. Starting at A, the nearest-neighbour algorithm gives the tour A→B→C→D→E→A with length 15.04 km, but the optimal tour A→B→E→C→D→A has length 13.04 km. Explain why the nearest-neighbour algorithm failed to find the optimal tour in this case.” Their response addresses only this point: “Explains that the nearest-neighbour algorithm makes the locally optimal choice at each step without considering the overall structure of the remaining route.” Evaluate the response against the complete 3-mark task. Identify what earns credit and state every additional requirement needed for full marks.

    [3 marks] · no calculator

    Marking points

    • Recognises credit for the stated point: Explains that the nearest-neighbour algorithm makes the locally optimal choice at each step without considering the overall structure of the remaining route.
    • Identifies the missing requirement: Explains that by visiting C and D before the distant point E, the algorithm is forced to make two long journeys to and from E (D to E and E back to A), rather than visiting E in a single efficient detour from B.
    • Identifies the missing requirement: Concludes that greedy, locally-optimal choices do not always lead to a globally optimal solution for the travelling salesman problem.

    Examiner tip: Treat each marking point as a separate requirement. Do not award the same idea twice, and do not infer work the learner did not show.

Original, unofficial practice questions from SubjectScout — not official past-paper questions.