IB · MATH AI HL

Mathematics: Applications & Interpretation HL

Graph theory and networks — Topic 3 HL

Name: ____________________Date: November 19, 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]

    Worked explanation

    1. The degree sum is 3+2+2+3+2=12; every undirected edge contributes two to that sum.
    2. Therefore edge count=12/2=6. The even degree sum is a necessary consistency check.

    Common mistake: The degree sum counts every edge twice.

    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.
    • Checks this criterion, crediting equivalent work already shown or identifying what is missing: Calculates the sum of degrees as 3+2+2+3+2 = 12, and divides by 2 to obtain 6 edges.

    Examiner tip: Check each criterion, including equivalent work already shown. Do not demand an extra step merely to rewrite an equivalent answer. Do not award the same idea twice or 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

    Worked explanation

    1. The proposed degrees sum to 3+2+2+2=9.
    2. An undirected graph must have degree sum 2E, an even integer. Since 9 is odd, no such simple graph exists.

    Common mistake: A sequence of individually permissible degrees may still fail the global parity condition.

    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.
    • Checks this criterion, crediting equivalent work already shown or identifying what is missing: 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: Check each criterion, including equivalent work already shown. Do not demand an extra step merely to rewrite an equivalent answer. Do not award the same idea twice or 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]

    Worked explanation

    1. In vertex order A,B,C,D, put 1 for each edge in both symmetric positions and 0 elsewhere: M=[[0,1,1,0],[1,0,1,1],[1,1,0,0],[0,1,0,0]].
    2. Row sums are 2,3,2,1, the respective degrees. Their total 8 equals twice the four edges.

    Common mistake: An undirected edge needs two symmetric matrix entries.

    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]].
    • Checks this criterion, crediting equivalent work already shown or identifying what is missing: Sums row A: 0+1+1+0 = 2, matching the degree of A (connected to B and C).
    • Checks this criterion, crediting equivalent work already shown or identifying what is missing: Sums row B: 1+0+1+1 = 3, matching the degree of B (connected to A, C, D).
    • Checks this criterion, crediting equivalent work already shown or identifying what is missing: Sums rows C and D similarly, confirming degrees 2 and 1 respectively.

    Examiner tip: Check each criterion, including equivalent work already shown. Do not demand an extra step merely to rewrite an equivalent answer. Do not award the same idea twice or 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]

    Worked explanation

    1. Kruskal adds lowest-weight edges without cycles: BC(1), AC(2), DE(2), EF(3); the equal-weight 2 edges may swap order.
    2. AB(4) would close A-B-C-A, so skip it; add BD(5) to join the two components. Five edges connect six vertices with total 1+2+2+3+5=13 km.

    Common mistake: Taking every short edge can create a cycle before the network is connected.

    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).
    • Checks this criterion, crediting equivalent work already shown or identifying what is missing: Adds BC(1): no cycle formed.
    • Checks this criterion, crediting equivalent work already shown or identifying what is missing: Adds AC(2): no cycle formed.
    • Checks this criterion, crediting equivalent work already shown or identifying what is missing: Adds DE(2): no cycle formed.
    • Checks this criterion, crediting equivalent work already shown or identifying what is missing: 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.
    • Checks this criterion, crediting equivalent work already shown or identifying what is missing: States the minimum spanning tree edges {BC, AC, DE, EF, BD} with total weight 1+2+2+3+5 = 13.

    Examiner tip: Check each criterion, including equivalent work already shown. Do not demand an extra step merely to rewrite an equivalent answer. Do not award the same idea twice or infer work the learner did not show.

  9. 9.

    An undirected network has roads AB=4, AC=2, BC=1, BD=5, CD=8, CE=10, DE=2, DF=6 and EF=3 km. Apply Prim's algorithm starting at A, showing the order in which vertices are added. State the selected edges and total weight, and compare with the Kruskal minimum-spanning-tree weight of 13 km.

    [6 marks]

    Worked explanation

    1. Prim from A adds C via AC(2), B via CB(1), D via BD(5), E via DE(2), F via EF(3). Vertex order: A,C,B,D,E,F.
    2. Edges total 2+1+5+2+3=13 km, equal to Kruskal's weight. Each choice is the cheapest edge crossing from the current tree to an outside vertex.

    Common mistake: Prim selects across the current tree boundary, not globally among all unused edges.

    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: “An undirected network has roads AB=4, AC=2, BC=1, BD=5, CD=8, CE=10, DE=2, DF=6 and EF=3 km. Apply Prim's algorithm starting at A, showing the order in which vertices are added. State the selected edges and total weight, and compare with the Kruskal minimum-spanning-tree weight of 13 km.” 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.
    • Checks this criterion, crediting equivalent work already shown or identifying what is missing: The cheapest edge from {A, C} to an outside vertex is BC(1), so B is added.
    • Checks this criterion, crediting equivalent work already shown or identifying what is missing: 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.
    • Checks this criterion, crediting equivalent work already shown or identifying what is missing: 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.
    • Checks this criterion, crediting equivalent work already shown or identifying what is missing: Lists the selected edges as {AC, BC, BD, DE, EF}.
    • Checks this criterion, crediting equivalent work already shown or identifying what is missing: Confirms the total weight 2+1+5+2+3 = 13, matching Kruskal's result.

    Examiner tip: Check each criterion, including equivalent work already shown. Do not demand an extra step merely to rewrite an equivalent answer. Do not award the same idea twice or 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]

    Worked explanation

    1. From P, tentative Q=7,R=9,U=14. Permanently label Q=7, then R=9; R improves U to 11 and S to 20.
    2. From U=11, improve T to 20. The shortest P-to-T route is P-R-U-T with length 9+2+9=20. Alternatives through S cannot improve it because S already costs 20.

    Common mistake: A direct edge to U at 14 is improved through R to 11.

    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.
    • Permanently labels Q with 7 and updates S to 7 + 15 = 22.
    • Permanently labels R with 9, updates U to 9 + 2 = 11 and improves S to 9 + 11 = 20.
    • Permanently labels U with 11 and updates T to 11 + 9 = 20.
    • S and T tie at 20, so either may be labelled next. Labelling S does not improve T, since 20 + 6 = 26. If T is selected first, the shortest-path search may stop there.
    • 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: For a network with nonnegative edge weights, permanently label a vertex with the smallest tentative distance, then relax all edges from that vertex before selecting the next one. Ties may be resolved in either order.

  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.
    • Checks this criterion, crediting equivalent work already shown or identifying what is missing: Permanently labels Q with 7 and updates S to 7 + 15 = 22.
    • Checks this criterion, crediting equivalent work already shown or identifying what is missing: Permanently labels R with 9, updates U to 9 + 2 = 11 and improves S to 9 + 11 = 20.
    • Checks this criterion, crediting equivalent work already shown or identifying what is missing: Permanently labels U with 11 and updates T to 11 + 9 = 20.
    • Checks this criterion, crediting equivalent work already shown or identifying what is missing: S and T tie at 20, so either may be labelled next. Labelling S does not improve T, since 20 + 6 = 26. If T is selected first, the shortest-path search may stop there.
    • Checks this criterion, crediting equivalent work already shown or identifying what is missing: Gives T a permanent label of 20, and backtracks the predecessors to find the path P → R → U → T.
    • Checks this criterion, crediting equivalent work already shown or identifying what is missing: States the shortest path as P → R → U → T with total length 20.

    Examiner tip: Check each criterion, including equivalent work already shown. Do not demand an extra step merely to rewrite an equivalent answer. Do not award the same idea twice or infer work the learner did not show.

  13. 13.

    For the undirected network PQ=7, PR=9, PU=14, QR=10, QS=15, RS=11, RU=2, ST=6 and UT=9, apply Dijkstra's algorithm from P until every vertex has a permanent label. State the labelling order, allowing either order when tentative distances tie, and identify the tied final distances.

    [2 marks]

    Worked explanation

    1. Set P=0, then permanent labels Q=7,R=9,U=11 after relaxing via PR and RU. R gives S=20 and U gives T=20.
    2. S and T tie at 20 and may be made permanent in either order; their mutual edge 6 offers no improvement. Final labels: P0,Q7,R9,U11,S20,T20.

    Common mistake: A tie permits either labelling order; it does not invalidate Dijkstra's algorithm.

    Marking points

    • States the order of permanent labelling as P, Q, R, U, then S and T (the two vertices tie at 20, so either order of S and T is acceptable).
    • Notes that S and T both receive a final permanent label of 20, so they are tied and the order between them does not affect the shortest distances found.

    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: “For the undirected network PQ=7, PR=9, PU=14, QR=10, QS=15, RS=11, RU=2, ST=6 and UT=9, apply Dijkstra's algorithm from P until every vertex has a permanent label. State the labelling order, allowing either order when tentative distances tie, and identify the tied final distances.” Their response addresses only this point: “States the order of permanent labelling as P, Q, R, U, then S and T (the two vertices tie at 20, so either order of S and T is acceptable).” 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, then S and T (the two vertices tie at 20, so either order of S and T is acceptable).
    • Checks this criterion, crediting equivalent work already shown or identifying what is missing: Notes that S and T both receive a final permanent label of 20, so they are tied and the order between them does not affect the shortest distances found.

    Examiner tip: Check each criterion, including equivalent work already shown. Do not demand an extra step merely to rewrite an equivalent answer. Do not award the same idea twice or 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]

    Worked explanation

    1. From W choose nearest unvisited V(8), then Z(4), then Y(2), then X(3), and return X-W(12).
    2. Tour W-V-Z-Y-X-W has length 8+4+2+3+12=29 km. A feasible tour provides an upper bound, not a proof of optimality.

    Common mistake: Include the closing return edge to the starting city.

    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).
    • Checks this criterion, crediting equivalent work already shown or identifying what is missing: From V, the nearest unvisited city is Z (4 km).
    • Checks this criterion, crediting equivalent work already shown or identifying what is missing: From Z, the nearest unvisited city is Y (2 km).
    • Checks this criterion, crediting equivalent work already shown or identifying what is missing: From Y, the nearest unvisited city is X (3 km); returns to W from X (12 km).
    • Checks this criterion, crediting equivalent work already shown or identifying what is missing: States the route W→V→Z→Y→X→W with total upper bound 8+4+2+3+12 = 29 km.

    Examiner tip: Check each criterion, including equivalent work already shown. Do not demand an extra step merely to rewrite an equivalent answer. Do not award the same idea twice or infer work the learner did not show.

  17. 17.

    Five cities have symmetric direct distances (km): WX=12, WY=10, WZ=19, WV=8, XY=3, XZ=7, XV=6, YZ=2, YV=20, ZV=4. Find a lower bound for a travelling-salesman tour by deleting W, finding a minimum spanning tree on the remaining cities and adding the two shortest edges incident to W. Compare it with the supplied nearest-neighbour upper bound of 29 km.

    [6 marks]

    Worked explanation

    1. Delete W. On X,Y,Z,V, Kruskal chooses YZ(2), XY(3), ZV(4), giving MST weight 9 km.
    2. The two shortest edges at W are WV=8 and WY=10. Lower bound=9+8+10=27 km, so with the supplied upper bound 27<=optimum<=29 km.
    3. Removing W from any tour leaves a spanning path, whose weight is at least the MST, plus two W-incident edges. This explains why the construction is a lower bound.

    Common mistake: The lower-bound construction need not itself form a valid tour.

    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 supplied upper bound of 29 km.

    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: “Five cities have symmetric direct distances (km): WX=12, WY=10, WZ=19, WV=8, XY=3, XZ=7, XV=6, YZ=2, YV=20, ZV=4. Find a lower bound for a travelling-salesman tour by deleting W, finding a minimum spanning tree on the remaining cities and adding the two shortest edges incident to W. Compare it with the supplied nearest-neighbour upper bound of 29 km.” 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.
    • Checks this criterion, crediting equivalent work already shown or identifying what is missing: Obtains the minimum spanning tree edges {YZ(2), XY(3), ZV(4)} with total weight 9.
    • Checks this criterion, crediting equivalent work already shown or identifying what is missing: Identifies the two shortest edges connected to W as WV(8) and WY(10).
    • Checks this criterion, crediting equivalent work already shown or identifying what is missing: Adds these to the minimum spanning tree weight: 9 + 8 + 10 = 27.
    • Checks this criterion, crediting equivalent work already shown or identifying what is missing: States the lower bound as 27 km.
    • Checks this criterion, crediting equivalent work already shown or identifying what is missing: Concludes that the optimal tour length lies between the lower bound 27 km and the supplied upper bound of 29 km.

    Examiner tip: Check each criterion, including equivalent work already shown. Do not demand an extra step merely to rewrite an equivalent answer. Do not award the same idea twice or 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]

    Worked explanation

    1. Original edge total=3+4+5+6=18 km. A closed traversal needs all degrees even, so duplicate the shortest path between odd vertices C and D: CD, length 6.
    2. Minimum length=24 km. One route is A-B-C-D-C-A with lengths 3+4+6+6+5=24, meeting the lower bound.

    Common mistake: The dead-end edge CD must be travelled back as well as out.

    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: In a connected undirected route-inspection problem with positive edge weights, an Eulerian network needs no repeated edges. Otherwise pair the odd-degree vertices to minimise the total added shortest-path length; with exactly two odd vertices, duplicate a shortest path between them.

  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.
    • Checks this criterion, crediting equivalent work already shown or identifying what is missing: Identifies the two odd-degree vertices as C and D (this is the Chinese postman problem).
    • Checks this criterion, crediting equivalent work already shown or identifying what is missing: Finds the shortest path between the two odd vertices C and D, which is the direct edge CD = 6.
    • Checks this criterion, crediting equivalent work already shown or identifying what is missing: Adds this shortest path weight to the total edge weight as the duplicated route: 18 + 6 = 24.
    • Checks this criterion, crediting equivalent work already shown or identifying what is missing: States the shortest route length as 24 km.

    Examiner tip: Check each criterion, including equivalent work already shown. Do not demand an extra step merely to rewrite an equivalent answer. Do not award the same idea twice or infer work the learner did not show.

  21. 21.

    For each of the following connected undirected graphs, classify whether it has an Euler circuit, an Euler trail but not a circuit, or neither, using its vertex degrees: (a) 4, 4, 2, 2, 2. (b) 3, 3, 2, 2. (c) 3, 3, 3, 3.

    [3 marks] · no calculator

    Worked explanation

    1. For a connected undirected graph, zero odd-degree vertices permits an Euler circuit; exactly two permits an open Euler trail only.
    2. (a) All degrees even: circuit. (b) Two odd degrees: trail but not circuit. (c) Four odd degrees: neither. Each case uses the given connectedness assumption.

    Common mistake: An even total degree is not enough for a circuit; every individual degree must be even.

    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: For a connected undirected graph, zero odd-degree vertices gives an Euler circuit, exactly two gives an Euler trail but no circuit, and more than two gives neither. Without connectedness of the non-isolated part, parity alone is insufficient.

  22. 22.

    Marking analysis: A learner attempts the following task: “For each of the following connected undirected graphs, classify whether it has an Euler circuit, an Euler trail but not a circuit, or neither, using its vertex degrees: (a) 4, 4, 2, 2, 2. (b) 3, 3, 2, 2. (c) 3, 3, 3, 3.” 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.
    • Checks this criterion, crediting equivalent work already shown or identifying what is missing: 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).
    • Checks this criterion, crediting equivalent work already shown or identifying what is missing: States that (c), with four vertices of odd degree, has neither an Euler circuit nor an Euler trail.

    Examiner tip: Check each criterion, including equivalent work already shown. Do not demand an extra step merely to rewrite an equivalent answer. Do not award the same idea twice or 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

    Worked explanation

    1. A tree is connected and acyclic. For n>1 remove a leaf and its single incident edge; the remaining graph is a tree on n-1 vertices.
    2. Starting from the one-vertex tree with zero edges, restoring each leaf adds exactly one edge, proving E=n-1. For n=6, E=5.

    Common mistake: Connectedness alone does not force n-1 edges; acyclicity is also needed.

    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.
    • Checks this criterion, crediting equivalent work already shown or identifying what is missing: Notes that adding any further edge to a tree would necessarily create a cycle, while removing any edge would disconnect it.
    • Checks this criterion, crediting equivalent work already shown or identifying what is missing: States that a tree with 6 vertices has 6 − 1 = 5 edges.

    Examiner tip: Check each criterion, including equivalent work already shown. Do not demand an extra step merely to rewrite an equivalent answer. Do not award the same idea twice or 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]

    Worked explanation

    1. Row-column multiplication gives M^2=[[2,1,1],[1,2,1],[1,1,2]].
    2. Entry (i,j) counts walks of length two from i to j. Each vertex has two ways to leave and return, while each distinct pair has one two-edge walk through the third vertex.

    Common mistake: Matrix powers count walks, which may repeat vertices, not only simple paths.

    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]].
    • Checks this criterion, crediting equivalent work already shown or identifying what is missing: Explains that each off-diagonal entry (i, j) of M² gives the number of walks of length 2 from vertex i to vertex j.
    • Checks this criterion, crediting equivalent work already shown or identifying what is missing: 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.
    • Checks this criterion, crediting equivalent work already shown or identifying what is missing: Verifies that the diagonal entries (all 2) match the degree of each vertex in this triangle graph.

    Examiner tip: Check each criterion, including equivalent work already shown. Do not demand an extra step merely to rewrite an equivalent answer. Do not award the same idea twice or infer work the learner did not show.

  27. 27.

    Define a Hamiltonian cycle. Find one in the complete undirected five-city network with distances (km) WX=12, WY=10, WZ=19, WV=8, XY=3, XZ=7, XV=6, YZ=2, YV=20, ZV=4, and state its total length.

    [3 marks]

    Worked explanation

    1. A Hamiltonian cycle visits every vertex exactly once before returning to its start.
    2. For example W-V-Z-Y-X-W visits all five cities and has weight 8+4+2+3+12=29 km. Other valid Hamiltonian cycles are possible; this definition does not require shortest length.

    Common mistake: Hamiltonian concerns vertices; Eulerian concerns traversing edges.

    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 a Hamiltonian cycle. Find one in the complete undirected five-city network with distances (km) WX=12, WY=10, WZ=19, WV=8, XY=3, XZ=7, XV=6, YZ=2, YV=20, ZV=4, and state 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.
    • Checks this criterion, crediting equivalent work already shown or identifying what is missing: States a valid Hamiltonian cycle, such as W→X→Y→Z→V→W.
    • Checks this criterion, crediting equivalent work already shown or identifying what is missing: 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: Check each criterion, including equivalent work already shown. Do not demand an extra step merely to rewrite an equivalent answer. Do not award the same idea twice or 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

    Worked explanation

    1. A tree is connected without cycles and has exactly n-1 edges on n vertices.
    2. Any connected graph has at least n-1 edges. If it has more, it contains a cycle; a general connected graph may also itself be a tree. Adding an edge to a tree closes a cycle along the existing unique path.

    Common mistake: A general connected graph is not necessarily cyclic; trees are a special case.

    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.
    • Checks this criterion, crediting equivalent work already shown or identifying what is missing: Notes that every tree is a connected graph, but not every connected graph is a tree.

    Examiner tip: Check each criterion, including equivalent work already shown. Do not demand an extra step merely to rewrite an equivalent answer. Do not award the same idea twice or infer work the learner did not show.

  31. 31.

    A complete weighted graph models travel between locations A, B, C, D and E. Its symmetric weights (km) are AB=BC=CD=DA=1, AC=BD=1.41, AE=DE=6.02 and BE=CE=5.02. Starting at A and breaking the initial tie by choosing B, nearest neighbour gives A-B-C-D-E-A with length 15.04 km. An optimal tour A-B-E-C-D-A has length 13.04 km. Explain why nearest neighbour misses an optimum in this case.

    [3 marks] · no calculator

    Worked explanation

    1. Nearest neighbour chooses the immediate 1 km links A-B-C-D, leaving costly D-E and E-A links. Its total is 1+1+1+6.02+6.02=15.04 km.
    2. A-B-E-C-D-A instead costs 1+5.02+5.02+1+1=13.04 km. Accepting a longer intermediate step avoids two expensive final connections; a locally cheapest choice need not minimise the full tour.

    Common mistake: A greedy rule guarantees a feasible tour, not a globally optimal one.

    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: Nearest neighbour is a heuristic: it need not find an optimal tour. A valid lower bound can help assess the quality of the upper bound it produces.

  32. 32.

    Marking analysis: A learner attempts the following task: “A complete weighted graph models travel between locations A, B, C, D and E. Its symmetric weights (km) are AB=BC=CD=DA=1, AC=BD=1.41, AE=DE=6.02 and BE=CE=5.02. Starting at A and breaking the initial tie by choosing B, nearest neighbour gives A-B-C-D-E-A with length 15.04 km. An optimal tour A-B-E-C-D-A has length 13.04 km. Explain why nearest neighbour misses an optimum 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.
    • Checks this criterion, crediting equivalent work already shown or identifying what is missing: 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.
    • Checks this criterion, crediting equivalent work already shown or identifying what is missing: Concludes that greedy, locally-optimal choices do not always lead to a globally optimal solution for the travelling salesman problem.

    Examiner tip: Check each criterion, including equivalent work already shown. Do not demand an extra step merely to rewrite an equivalent answer. Do not award the same idea twice or infer work the learner did not show.