Graph theory and networks

Paper labels are an unofficial, independently authored grouping, applied only where a question's own format genuinely matches a real paper convention (such as IB Mathematics AA's non-calculator/calculator split). They do not reproduce any exam board's real paper numbering or mark allocation, and uncertain questions are labelled general practice instead.

• 1A simple graph has vertices with degrees 3, 2, 2, 3, 2. Use the handshaking lemma to find the number of edges in the graph.Paper 1 styleEasy2 marksCalculator+
• 2Marking 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.Marking analysisEasy2 marksCalculator+
• 3Explain why no simple graph can have the degree sequence 3, 2, 2, 2.Paper 1 styleEasy2 marksNo calculator+
• 4Marking 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.Marking analysisEasy2 marksNo calculator+
• 5A 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.Paper 1 styleMedium4 marksCalculator+
• 6Marking 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.Marking analysisMedium4 marksCalculator+
• 7A 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.Paper 2 styleHard6 marksCalculator+
• 8Marking 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.Marking analysisHard6 marksCalculator+
• 9Using 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.Paper 2 styleHard6 marksCalculator+
• 10Marking 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.Marking analysisHard6 marksCalculator+
• 11A 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.Paper 3 style (extended)Hard7 marksCalculator+
• 12Marking 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.Marking analysisHard7 marksCalculator+
• 13Using 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.Paper 2 styleEasy2 marksCalculator+
• 14Marking 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.Marking analysisEasy2 marksCalculator+
• 15Five 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.Paper 2 styleMedium5 marksCalculator+
• 16Marking 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.Marking analysisMedium5 marksCalculator+
• 17Using 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.Paper 3 style (extended)Hard6 marksCalculator+
• 18Marking 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.Marking analysisHard6 marksCalculator+
• 19A 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.Paper 2 styleMedium5 marksCalculator+
• 20Marking 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.Marking analysisMedium5 marksCalculator+
• 21For 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).Paper 1 styleEasy3 marksNo calculator+
• 22Marking 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.Marking analysisEasy3 marksNo calculator+
• 23Explain why a tree with n vertices always has exactly n − 1 edges, and state the number of edges in a tree with 6 vertices.Paper 1 styleEasy3 marksNo calculator+
• 24Marking 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.Marking analysisEasy3 marksNo calculator+
• 25A 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.Paper 2 styleMedium4 marksCalculator+
• 26Marking 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.Marking analysisMedium4 marksCalculator+
• 27Define 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.Paper 1 styleEasy3 marksCalculator+
• 28Marking 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.Marking analysisEasy3 marksCalculator+
• 29Explain 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.Paper 1 styleEasy2 marksNo calculator+
• 30Marking 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.Marking analysisEasy2 marksNo calculator+
• 31Five 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.Paper 2 styleEasy3 marksNo calculator+
• 32Marking 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.Marking analysisEasy3 marksNo calculator+