Free worked solutions · 2026 Edition

IB Maths AI HL Chapter 12: Graph theory worked solutions

Worked solutions to the practice questions in Chapter 12 of Photon Guidebook: Mathematics Applications and Interpretation HL for the IB Diploma (2026 Edition). Each solution shows every step with the mark it earns, the way an IB mark scheme does.

  • Chapter 12 of 24
  • Volume 1
  • 26 practice questions
  • 3 Going further
  • Free, no sign-up
Start with Basics All 24 chapters

Basics

One idea at a time, in the order the chapter teaches them.

Question 1

[3 marks]
A complete simple graph connects every pair of distinct vertices once. There are seven vertices.
Calculate the degree of each vertex and the number of edges.
[3]
Show solutionHide solution
Each vertex has degree 6.
A1
Edge count =7(6)/2=21. M1A1

Final answer

Each vertex has degree 6; 21 edges.

Question 2

[3 marks]
A simple undirected graph has adjacency matrix M=\begin{pmatrix}0&1&a\\1&0&1\\b&1&0\end{pmatrix}. There is no edge between the first and third vertices.
Find a,b and explain the symmetry of an undirected adjacency matrix.
[3]
Show solutionHide solution
a=b=0.
A2
An edge works both ways, so m_{ij}=m_{ji}.
R1

Final answer

a=b=0. An edge works both ways, so the matrix is symmetric about its diagonal.

Question 3

[5 marks]
A triangular cycle network has adjacency matrix M=\begin{pmatrix}0&1&1\\1&0&1\\1&1&0\end{pmatrix} in alphabetical vertex order. The entry (i,j) of M^n counts walks of length n from i to j.
(a) Find M^2 and hence the number of length-2 walks from A to B.
[4]
(b) Explain why a walk may repeat a vertex.
[1]
Show solutionHide solution
(a) M^2=\begin{pmatrix}2&1&1\\1&2&1\\1&1&2\end{pmatrix}. M1A2
The required entry is 1, so there are 1 walks.
A1
(b) A walk is a sequence of adjacent vertices; repeats are permitted.
R1

Final answer

(a) M^2=\begin{pmatrix}2&1&1\\1&2&1\\1&1&2\end{pmatrix}; 1 walk from A to B. (b) A walk is any sequence of edges, so it may pass through a vertex more than once.

Question 4

[2 marks]
A connected road network has vertex degrees 2,4,4,6,2.
Explain why a closed inspection route can traverse each road exactly once.
[2]
Show solutionHide solution
Every degree is even. R1 Together with connectivity this guarantees an Eulerian circuit covering each edge once.
R1

Final answer

The network is connected and every degree is even, so an Eulerian circuit exists.

Question 5

[4 marks]
Between laboratory rooms K,L,M,N,O, cable costs are KL=19,KM=24,LM=17,LN=28,MN=21,MO=32,NO=23 dollars.
Use Kruskal's algorithm to give a cheapest connecting network and its cost.
[4]
Show solutionHide solution
Accept LM,KL,MN,NO in increasing order. M1 A1 These four edges connect all five rooms without cycles. R1 Cost 17+19+21+23=80 dollars.
A1

Final answer

LM, KL, MN, NO; 80 dollars.

Question 6

[4 marks]
A network has AB=238,AC=136,BC=187,BD=102,CD=289,CE=153,DE=221.
Use Prim's algorithm from E. Explain why BD cannot be selected first.
[4]
Show solutionHide solution
From E: EC, then CA, then CB, then BD. M1 A1 Total 153+136+187+102=578. A1 The first edge must touch E; BD does not.
R1

Final answer

EC, CA, CB, BD; 578. BD does not touch E, so it cannot be chosen first.

Question 7

[4 marks]
Four odd vertices P,Q,R,S have shortest path lengths PQ=148,PR=167,PS=213,QR=189,QS=156,RS=174 metres. Total road length is 1649 metres.
Find the optimal repeated-path pairing and inspection length.
[4]
Show solutionHide solution
Pairing totals: PQ+RS=322, PR+QS=323, PS+QR=402. M1 A1 Repeat shortest PQ and RS paths. A1 Length 1649+322=1971 m.
A1

Final answer

Repeat PQ and RS (322, the least pairing); 1649+322=1971 m.

Question 8

[4 marks]
Between five sites, lengths are AB=31,AC=46,AD=59,AE=64,BC=38,BD=52,BE=61,CD=35,CE=49,DE=42.
Apply nearest neighbour from C and state a complete tour and its length.
[4]
Show solutionHide solution
C-D-E-B-A-C. M1 A1 Length 35+42+61+31+46=215.
M1A1

Final answer

C, D, E, B, A, C; 215.

Question 9

[4 marks]
A complete graph has AB=56,AC=71,AD=89,BC=62,BD=77,CD=68.
Delete A to obtain a travelling-salesperson lower bound. Show the tree and the two reattachment edges.
[4]
Show solutionHide solution
MST on B,C,D is BC,CD, weight 130. M1 A1 Two cheapest edges incident to A are AB,AC, sum 127. M1 Lower bound 130+127=257.
A1

Final answer

Tree BC 62 and CD 68, weight 130, plus AB 56 and AC 71 (127): lower bound 257.

Question 10

[3 marks]
Deleting each of four vertices gives lower bounds 318, 327, 321 and 325. Feasible tours have weights 342 and 335.
Give the strongest interval for the minimum tour weight. Does this prove the 335-weight tour is optimal?
[3]
Show solutionHide solution
Use the largest lower bound and smallest upper bound: 327\leq L\leq335. M1 A1 No; a shorter tour between 327 and 335 has not been ruled out.
R1

Final answer

327\le L\le335. No: the bounds do not prove that the tour of weight 335 is shortest.

Tutorial

Exam-style questions on each question type, with the marks the IB would give.

Question 11

[8 marks]
Marcus, a network engineer, wants to connect seven servers so that every server is joined directly to exactly three others.
(a) Use the handshaking lemma to show that Marcus's plan is impossible.
[2]
Marcus's club later runs a round-robin tournament in which each of 9 players plays every other player exactly once.
(b) Represent the tournament as a complete graph and find the total number of matches played.
[2]
(c) Another round-robin has 190 matches in total. Find the number of players.
[2]
(d) Explain why, in any graph, the number of vertices of odd degree must be even.
[2]
Show solutionHide solution
(a) Seven vertices of degree 3 would give \sum \deg(v) = 7 \times 3 = 21. [1] But \sum \deg(v) = 2e is always even, and 21 is odd, so no such graph exists.
[1]
(b) The complete graph K_9 has one edge for each pair of players: \dfrac{9 \times 8}{2} = 36 matches.
[2]
(c) \dfrac{n(n-1)}{2} = 190 \Rightarrow n(n-1) = 380 \Rightarrow n^2 - n - 380 = 0. [1] Solving on the GDC (or factorising (n-20)(n+19)) gives n = 20, rejecting the negative root.
[1]
(d) The sum of all degrees is even. [1] The even-degree vertices add an even amount, so the odd-degree vertices must also add up to an even number; a sum of odd numbers is even only if there is an even number of them.
[1]

Final answer

(a) The degrees would add up to 7\times3=21, which is odd. (b) 36 matches. (c) 20 players. (d) Each edge adds 2 to the sum of the degrees, so the sum is even and the odd degrees come in pairs.

Question 12

[7 marks]
The floor plan of a museum has six galleries, A to F. Each corridor joins two galleries and is shown as an edge.
Original Photon diagram
(a) Show that it is possible to walk along every corridor exactly once and finish in the gallery where you started.
[2]
(b) Write down a route that visits every gallery exactly once and returns to its start.
[1]
(c) A cleaning robot must travel along every corridor; a visitor wants to see every gallery once. Name the type of route each needs.
[2]
(d) The corridor between A and B is closed for repairs. Determine whether the robot can still travel along every remaining corridor exactly once, and if so state where it must start and finish.
[2]
Show solutionHide solution
(a) Every vertex has degree 4, an even number. [1] A connected graph with all degrees even has an Eulerian circuit, so such a route exists.
[1]
(b) For example A \to B \to C \to D \to E \to F \to A (a Hamiltonian cycle).
[1]
(c) The robot needs an Eulerian trail or circuit (every edge once). [1] The visitor needs a Hamiltonian path or cycle (every vertex once).
[1]
(d) Removing AB leaves A and B with degree 3 (odd) and every other vertex even degree. [1] Exactly two odd vertices, so an Eulerian trail exists; it must start at A and finish at B (or the reverse).
[1]

Final answer

(a) Every degree is 4 and the graph is connected. (b) A, B, C, D, E, F, A. (c) Eulerian circuit; Hamiltonian cycle. (d) Yes: A and B become odd, so start at A and finish at B.

Question 13

[7 marks]
Five islands, A to E, in a theme-park lagoon are connected by rope bridges as shown. Each trip over a bridge from one island to a neighbouring island is one crossing.
Original Photon diagram
(a) Write down the adjacency matrix, with the vertices in the order A, B, C, D, E.
[2]
(b) Use your GDC to find the number of different routes from island A to island E that consist of exactly 4 crossings.
[2]
(c) Find the number of routes that start at C and consist of exactly 3 crossings and end at C. Explain why this number is even.
[3]
Show solutionHide solution
(a)
\begin{array}{c c} & \begin{array}{ccccc} \text{A} & \text{B} & \text{C} & \text{D} & \text{E} \end{array} \\ \begin{array}{c} \text{A}\\\text{B}\\\text{C}\\\text{D}\\\text{E} \end{array} & \left(\begin{array}{ccccc} 0 & 1 & 1 & 1 & 0 \\ 1 & 0 & 1 & 0 & 0 \\ 1 & 1 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 1 & 0 \end{array}\right) \end{array}
[2]
(b) A^4 from the GDC, entry in row A, column E: 11.
[2]
A^4 = \begin{pmatrix}15 & 8 & 7 & 3 & 11 \\ 8 & 8 & 8 & 6 & 6 \\ 7 & 8 & 15 & 11 & 3 \\ 3 & 6 & 11 & 9 & 1 \\ 11 & 6 & 3 & 1 & 9\end{pmatrix}
(c) Entry in row C, column C of A^3 is 2. [2] Closed walks of length 3 from C must travel round a triangle (here A–B–C) in one of its two directions.
[1]
The triangle ABC gives C \to A \to B \to C and C \to B \to A \to C.

Final answer

(a) M=\begin{pmatrix}0&1&1&1&0\\1&0&1&0&0\\1&1&0&0&1\\1&0&0&0&1\\0&0&1&1&0\end{pmatrix}. (b) 11. (c) 2: round triangle ABC in either direction; reversing a route gives another.

Question 14

[8 marks]
Five villages, A to E, on a mountain are linked by one-way cable-car lines as shown. The operator wants to guarantee that a passenger can get from any village to any other village using a limited number of rides.
Original Photon diagram
(a) Write down the adjacency matrix M and use your GDC to find M + M^2.
[3]
(b) Hence show that it is not always possible to get from one village to another using at most 2 rides, naming one pair of villages that cannot be linked in this way.
[2]
(c) Find the smallest number k such that every village can be reached from every other village using at most k rides. Justify your answer using a matrix.
[3]
Show solutionHide solution
(a)
M = \begin{array}{c c} & \begin{array}{ccccc} \text{A} & \text{B} & \text{C} & \text{D} & \text{E} \end{array} \\ \begin{array}{c} \text{A}\\\text{B}\\\text{C}\\\text{D}\\\text{E} \end{array} & \left(\begin{array}{ccccc} 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 1 & 1 \\ 1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 \end{array}\right) \end{array}
[1]
M + M^2 = \begin{pmatrix}0 & 1 & 1 & 1 & 1 \\ 2 & 1 & 1 & 1 & 1 \\ 1 & 1 & 0 & 0 & 0 \\ 0 & 1 & 1 & 1 & 1 \\ 1 & 1 & 0 & 0 & 0\end{pmatrix}
[2]
(b) Row C, column D of M + M^2 is 0, so there is no walk of at most 2 rides from C to D (and so not every pair can be linked).
[2]
(c) M + M^2 + M^3 = \begin{pmatrix}2 & 2 & 1 & 1 & 1 \\ 2 & 3 & 2 & 2 & 2 \\ 1 & 1 & 1 & 1 & 1 \\ 2 & 2 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 & 1\end{pmatrix}, in which every off-diagonal entry is positive. [2] Since k = 2 fails by (b), the smallest value is k = 3.
[1]

Final answer

(a) M=\begin{pmatrix}0&1&0&0&0\\0&0&1&1&1\\1&0&0&0&0\\0&1&0&0&0\\1&0&0&0&0\end{pmatrix}. (b) C to D has entry 0 in M+M^2. (c) k=3.

Question 15

[9 marks]
A school robotics club has a website with four pages: Home (H), Events (E), Shop (S) and Contact (C). The arrows show the links between pages. A visitor on a page clicks one of its links, chosen at random with equal probability, and the visitor never leaves the site.
Original Photon diagram
(a) Write down the transition matrix M (states in the order H, E, S, C; each column gives the probabilities of clicking from that page).
[3]
(b) A visitor starts on the Contact page. Find the probability that she is on the Home page after 4 clicks.
[2]
(c) Use your GDC to find the long-run proportion of visits to each page, and state which page is visited most.
[3]
(d) State one assumption made by this model that may not hold for real visitors.
[1]
Show solutionHide solution
(a) M = \begin{pmatrix}0 & \frac{1}{2} & 1 & 0 \\ \frac{1}{3} & 0 & 0 & 1 \\ \frac{1}{3} & 0 & 0 & 0 \\ \frac{1}{3} & \frac{1}{2} & 0 & 0\end{pmatrix}
[3]
(b) The visitor starts on C, so s_0 = (0,0,0,1)^T and s_4 = M^4 s_0 = (0.5,\ 0.1667,\ 0,\ 0.3333)^T (GDC). [1] The probability of being on the Home page is the first entry, 0.5 (that is \frac{1}{2}).
[1]
(c) Raising M to a high power (e.g. M^{80}), every column becomes (0.2727,\ 0.3636,\ 0.0909,\ 0.2727)^T. [2] These are \frac{3}{11},\frac{4}{11},\frac{1}{11},\frac{3}{11}; the Events page is visited most (about 36.4% of the time).
[1]
(d) Visitors choose links with equal probability, whereas real visitors prefer some links (or stop browsing).
[1]

Final answer

(a) M=\begin{pmatrix}0&\frac12&1&0\\\frac13&0&0&1\\\frac13&0&0&0\\\frac13&\frac12&0&0\end{pmatrix}. (b) \frac12. (c) \frac3{11},\frac4{11},\frac1{11},\frac3{11}: Events is visited most (36.4%). (d) For example, the visitor chooses links at random.

Question 16

[7 marks]
A broadband provider wants to connect six villages, A to F, to its network with the least total length of cable. The possible links are shown, with lengths in kilometres.
Original Photon diagram
(a) Use Kruskal's algorithm to find a minimum spanning tree. State the order in which the edges are considered, and for each edge say whether it is added or rejected.
[4]
(b) Draw the minimum spanning tree and state its total length.
[2]
(c) Explain how you know that your tree contains no cycle and reaches every village.
[1]
Show solutionHide solution
(a) Sorted: DE (8), BC (9), EF (11), CD (12), AB (14), BD (17), DF (19), AC (22), CE (25).
[1]
\begin{array}{|c|c|l|} \hline \text{Edge} & \text{Weight} & \text{Decision} \\ \hline \text{DE} & \text{8} & \text{add} \\ \hline \text{BC} & \text{9} & \text{add} \\ \hline \text{EF} & \text{11} & \text{add} \\ \hline \text{CD} & \text{12} & \text{add} \\ \hline \text{AB} & \text{14} & \text{add} \\ \hline \text{BD} & \text{17} & \text{not needed (tree complete)} \\ \hline \text{DF} & \text{19} & \text{not needed (tree complete)} \\ \hline \text{AC} & \text{22} & \text{not needed (tree complete)} \\ \hline \text{CE} & \text{25} & \text{not needed (tree complete)} \\ \hline \end{array}
[3]
(b) Edges DE, BC, EF, CD, AB, total 8+9+11+12+14 = 54 km.
[1]
Original Photon diagram
[1]
(c) It has 6 - 1 = 5 edges, and each edge was only accepted when it joined two separate pieces (no cycle); 5 such edges join all six villages.
[1]

Final answer

DE, BC, EF, CD, AB; 54 km.

Question 17

[8 marks]
A refuse collection truck must drive along every one of the roads shown, which join six depots A to F, starting and finishing at A. The weights are lengths in kilometres.
Original Photon diagram
(a) Write down the vertices of odd degree.
[1]
(b) List the three ways of pairing the odd vertices, and for each pairing find the total of the shortest distances between the pairs.
[4]
(c) Hence find the length of the shortest route that covers every road, and state which roads are repeated.
[3]
Show solutionHide solution
(a) A, B, E and F have degree 3; C has degree 2 and D has degree 4.
[1]
(b) Shortest distances: AB = 11, EF = 26 (via D: 12 + 14), AE = 16 (via C: 10 + 6), BF = 19 (via D: 5 + 14), AF = 23 (via D: 9 + 14), BE = 13.
[2]
\begin{array}{|l|c|} \hline \text{Pairing} & \text{Total} \\ \hline \text{AB + EF} & 11 + 26 = 37 \\ \hline \text{AE + BF} & 16 + 19 = 35 \\ \hline \text{AF + BE} & 23 + 13 = 36 \\ \hline \end{array}
[2]
(c) The smallest is AE + BF = 35. The roads sum to 11 + 12 + 10 + 6 + 9 + 13 + 14 + 5 = 80. [1] Shortest route = 80 + 35 = 115 km. [1] The repeated roads are AC, CE (for A to E) and BD, DF (for B to F).
[1]

Final answer

(a) A, B, E, F. (b) AB + EF =37; AE + BF =35; AF + BE =36. (c) 115 km, repeating AC, CE, BD and DF. (F has degree 1, which is still odd.)

Question 18

[6 marks]
The refuse collection truck of the previous question must again drive along every road of the network below (lengths in kilometres). The depot manager now allows the truck to start at one depot and finish at a different one.
Original Photon diagram
(a) Explain why the truck should start and finish at two of the odd-degree vertices.
[1]
(b) For each way of choosing the start and finish from the odd vertices, find the shortest route length. Hence find which two vertices are best, and the shortest possible route length.
[4]
(c) State the saving compared with a route that starts and finishes at the same depot.
[1]
Show solutionHide solution
(a) With the ends at two odd vertices those two need no repeated edge; only the other two odd vertices have to be paired, which needs fewer repeated roads.
[1]
(b) Roads sum to 80. The route length is 80 plus the shortest distance between the two odd vertices that are not the ends: ends E, F: 80 + AB = 91; ends A, F: 80 + BE = 93; ends B, F: 80 + AE = 96; ends A, E: 80 + BF = 99; ends B, E: 80 + AF = 103; ends A, B: 80 + EF = 106. [3] The best choice is to start at E and finish at F (or the reverse), with a shortest route of 91 km.
[1]
(c) The best closed route (previous question) is 115 km, so the saving is 115 - 91 = 24 km.
[1]

Final answer

(a) Start and finish at two odd vertices, so only the other two are repeated. (b) Start at E and finish at F; 91 km. (c) 24 km.

Question 19

[8 marks]
A delivery company has used the nearest neighbour algorithm and the deleted vertex algorithm on a table of least travel times (in minutes) for six depots. They found an upper bound of 238 minutes and a lower bound of 214 minutes for the shortest tour that visits every depot once.
(a) Ravi says the shortest possible tour takes 205 minutes. Explain why he must be wrong.
[1]
(b) Mei says there might be a tour of 230 minutes. State whether the bounds allow this, and whether they prove it.
[2]
(c) Tom finds a tour of length exactly 214 minutes. Explain what this proves.
[1]
(d) Find the greatest possible percentage by which the upper bound exceeds the true shortest time, to 3 significant figures.
[2]
(e) The company repeats the deleted vertex algorithm deleting each of the other depots, and also runs nearest neighbour from each other depot. Explain how it should combine the results.
[2]
Show solutionHide solution
(a) The shortest tour is at least the lower bound, 214, and 205 < 214.
[1]
(b) 214 \le 230 \le 238, so 230 is not ruled out. [1] But the bounds do not prove that such a tour exists.
[1]
(c) A tour of length 214 is a valid tour that equals the lower bound, so no tour can be shorter: it is the optimal tour.
[1]
(d) \dfrac{238 - 214}{214} \times 100 = 11.2\%.
[2]
(e) Take the largest of the lower bounds (the strongest) and the smallest of the upper bounds (the best tour found).
[2]

Final answer

(a) The tour cannot be shorter than 214. (b) 230 is allowed but not proved. (c) That tour is optimal. (d) 11.2%. (e) Take the largest lower bound and the smallest upper bound.

Question 20

[5 marks]
A courier firm has five depots, P to T. An assistant has produced the table of least distances (in km) between the depots, but one entry is wrong.
\begin{array}{|c|c|c|c|c|c|} \hline & \text{\textbf{P}} & \text{\textbf{Q}} & \text{\textbf{R}} & \text{\textbf{S}} & \text{\textbf{T}} \\ \hline \text{\textbf{P}} & \text{---} & \text{9} & \text{14} & \text{21} & \text{29} \\ \hline \text{\textbf{Q}} & \text{9} & \text{---} & \text{6} & \text{12} & \text{14} \\ \hline \text{\textbf{R}} & \text{14} & \text{6} & \text{---} & \text{15} & \text{8} \\ \hline \text{\textbf{S}} & \text{21} & \text{12} & \text{15} & \text{---} & \text{7} \\ \hline \text{\textbf{T}} & \text{29} & \text{14} & \text{8} & \text{7} & \text{---} \\ \hline \end{array}
(a) Find the entry that is wrong, by finding a route between two depots that is shorter than the table value. Show your route and its length.
[2]
(b) State the correct entry.
[1]
(c) Explain why, in any table of least distances, d(X, Z) \le d(X, Y) + d(Y, Z) for every three depots X, Y, Z.
[2]
Show solutionHide solution
(a) The entry P–T = 29 is too large: the route P \to R \to T has length 14 + 8 = 22 < 29.
[2]
(b) Other routes are longer (P \to Q \to R \to T = 9 + 6 + 8 = 23), so the correct entry is 22.
[1]
(c) The route from X to Y then Y to Z is a route from X to Z, so it cannot be shorter than the least distance from X to Z.
[2]

Final answer

P to T should be 22 km (P, R, T).

Mastery

Full exam questions that mix question types, at Paper 1 and Paper 2 standard.

Question 21

[7 marks]
An irrigation engineer must connect five field valves V_1,\dots,V_5 with pipe so all are linked using minimum total pipe. The distances (in metres) between valves that can be joined are given in the table; a dash means no direct pipe is possible.
V_1V_2V_3V_4V_5
V_1–6–9–
V_26–710–
V_3–7–85
V_49108–4
V_5––54–
Original Photon diagram
(a) Starting from V_1, apply Prim's algorithm. List the edges in the order they are added.
[4]
(b) Find the total length of pipe required.
[1]
(c) State how many edges a spanning tree of this network must contain, and explain why.
[2]
Show solutionHide solution
(a) Prim's grows a tree from V_1, each step adding the cheapest edge from the tree to a new vertex.
From \{V_1\}: cheapest is V_1V_2 (6). Tree \{V_1,V_2\}.
From \{V_1,V_2\}: options V_1V_4(9), V_2V_3(7), V_2V_4(10); add V_2V_3 (7). Tree \{V_1,V_2,V_3\}.
Now options include V_3V_5(5), V_3V_4(8), V_1V_4(9); add V_3V_5 (5). Tree \{V_1,V_2,V_3,V_5\}.
Finally cheapest to V_4 is V_5V_4 (4); add V_4V_5 (4).
Order added: V_1V_2,\ V_2V_3,\ V_3V_5,\ V_4V_5.
[4]
(b) Total =6+7+5+4=22 metres.
[1]
(c) A spanning tree of n vertices has n-1 edges. Here n=5, so 4 edges: this is the fewest edges that connect all vertices, and any more would create a cycle.
[2]

Final answer

V1V2, V2V3, V3V5, V5V4; 22 m; 4 edges, because a tree on 5 vertices has 5-1 edges.

Question 22

[10 marks]
A mail carrier must walk along every street of a small district at least once and return to the sorting office at P. The streets and their lengths (in metres) are shown below.
Original Photon diagram
(a) Find the total length of all the streets.
[1]
(b) (i) Write down the degree of every vertex.
[2]
(ii) List the vertices of odd degree.
[1]
(c) There are three ways of pairing the odd vertices. For each pairing, find the total of the shortest distances between the paired vertices.
[4]
(d) Hence find the length of the shortest closed route that covers every street of the district.
[2]
Show solutionHide solution
(a) Total =200+300+150+250+350+400+200+300+250+450=2850 m.
[1]
(b)(i) Degrees: P=3, Q=3, R=4, S=5, T=3, U=2.
[2]
(ii) Odd vertices: P, Q, S, T.
[1]
(c) Shortest distances between odd pairs: PQ=200, ST=200, QS=250, PS=450, QT=Q\!-\!S\!-\!T=450, PT=P\!-\!S\!-\!T=650. The three pairings:
\{PQ, ST\}=200+200=400; \{PS, QT\}=450+450=900; \{PT, QS\}=650+250=900.
The smallest total is 400 (pairing P with Q and S with T).
[4]
(d) Shortest closed route = total streets + smallest pairing =2850+400=3250 m.
[2]

Final answer

(a) 2850 m. (b) P 3, Q 3, R 4, S 5, T 3, U 2; odd: P, Q, S, T. (c) PQ + ST =400; PS + QT =900; PT + QS =900. (d) 3250 m.

Question 23

[7 marks]
The council in the earlier question on refuse collection is considering building a new road between depots A and E of length y km (shown dashed). Before the new road, the shortest route covering every road, starting and finishing at A, is 115 km.
Original Photon diagram
(a) State which vertices have odd degree once the new road is built.
[1]
(b) Find, in terms of y, the length of the shortest route that covers every road including the new one, starting and finishing at A.
[3]
(c) Find the range of values of y for which building the new road reduces the length of the shortest route.
[2]
(d) Find the saving if y = 12.
[1]
Show solutionHide solution
(a) The new road raises the degrees of A and E by 1 each, so they become even; B and F remain the only odd vertices.
[1]
(b) Roads now sum to 80 + y. [1] B and F must be paired: the least distance is 19 (B-D-F). [1] Shortest route = 80 + y + 19 = 99 + y.
[1]
(c) 99 + y < 115 \Rightarrow y < 16, and y > 0 so 0 < y < 16.
[2]
(d) New route = 99 + 12 = 111, a saving of 115 - 111 = 4 km.
[1]

Final answer

(a) B and F. (b) 99+y km. (c) 0<y<16. (d) 4 km.

Question 24

[8 marks]
A drone service flies between a central hub H and three depots X, Y and Z. Each flight goes from the hub to a depot or from a depot to the hub; there are no flights between depots.
(a) Write down the adjacency matrix M in the order H, X, Y, Z.
[2]
(b) Find M^3 and show that M^3=3M.
[2]
(c) Hence write down M^{2n+1} in terms of M and n.
[1]
(d) Find the number of different sequences of 9 flights that start at depot X and end at the hub.
[1]
(e) Find, in terms of n, the number of different sequences of 2n flights that start and end at the hub.
[2]
Show solutionHide solution
(a) M=\begin{pmatrix}0&1&1&1\\1&0&0&0\\1&0&0&0\\1&0&0&0\end{pmatrix}.
A2
(b) M^2=\begin{pmatrix}3&0&0&0\\0&1&1&1\\0&1&1&1\\0&1&1&1\end{pmatrix} and M^3=\begin{pmatrix}0&3&3&3\\3&0&0&0\\3&0&0&0\\3&0&0&0\end{pmatrix}=3M.
M1A1
(c) M^{2n+1}=3^nM.
A1
(d) M^9=3^4M, so the entry (X, H) is 81.
A1
(e) M^{2n}=3^{n-1}M^2.
M1
The entry (H, H) is 3^{n-1}\times3=3^n.
A1

Final answer

(a) M=\begin{pmatrix}0&1&1&1\\1&0&0&0\\1&0&0&0\\1&0&0&0\end{pmatrix}. (b) Shown. (c) M^{2n+1}=3^nM. (d) 81. (e) 3^n.

Question 25

[16 marks]
Four relay stations A, B, C and D pass messages along one-way links as shown. Each time a station relays a message, it sends it along one of its outgoing links, chosen at random with equal probability.
Original Photon diagram
(a) Write down the adjacency matrix (order A, B, C, D; row = sending station).
[2]
(b) Find the number of different paths of exactly 4 relays from A to D.
[2]
(c) Find the number of ways a message can start at a station and return to it after exactly 4 relays, the station being any of the four.
[2]
(d) Write down the transition matrix M for the random relaying.
[3]
(e) A message starts at A. Find the probability that it is at D after 4 relays.
[2]
(f) Find the long-run proportion of time a message spends at each station, using Ms = s, and state which station is busiest.
[3]
(g) Explain why your answer to part (b) cannot be used to find a probability in this network by dividing by a single constant.
[2]
Show solutionHide solution
(a)
\begin{array}{c c} & \begin{array}{cccc} \text{A} & \text{B} & \text{C} & \text{D} \end{array} \\ \begin{array}{c} \text{A}\\\text{B}\\\text{C}\\\text{D} \end{array} & \left(\begin{array}{cccc} 0 & 1 & 1 & 0 \\ 0 & 0 & 1 & 1 \\ 1 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 \end{array}\right) \end{array}
[2]
(b) (A^4)_{AD} = 2.
[2]
(c) Trace of A^4 = 1 + 1 + 1 + 1 = 4.
[2]
(d) M = \begin{pmatrix}0 & 0 & 1 & \frac{1}{2} \\ \frac{1}{2} & 0 & 0 & \frac{1}{2} \\ \frac{1}{2} & \frac{1}{2} & 0 & 0 \\ 0 & \frac{1}{2} & 0 & 0\end{pmatrix} (each column sums to 1).
[3]
(e) M^4 (1,0,0,0)^T = (0.25,\ 0.1875,\ 0.375,\ 0.1875)^T (GDC), so the probability of being at D after 4 relays is 0.1875 = \frac{3}{16}.
[2]
(f) M^{100} has every column (0.3529,\ 0.2353,\ 0.2941,\ 0.1176)^T. [2] These are \frac{6}{17}, \frac{4}{17}, \frac{5}{17}, \frac{2}{17}; A is the busiest.
[1]
(g) Stations have different numbers of outgoing links (A, B, D have 2, C has 1), so different walks of the same length have different probabilities.
[2]

Final answer

(a) M=\begin{pmatrix}0&1&1&0\\0&0&1&1\\1&0&0&0\\1&1&0&0\end{pmatrix}. (b) 2. (c) 4. (d) M=\begin{pmatrix}0&0&1&\frac12\\\frac12&0&0&\frac12\\\frac12&\frac12&0&0\\0&\frac12&0&0\end{pmatrix}. (e) \frac3{16}. (f) \frac6{17},\frac4{17},\frac5{17},\frac2{17}: A is busiest. (g) The stations have different numbers of outgoing links, so the paths are not equally likely.

Question 26

[18 marks]
A mobile library van is based at a depot D and visits five villages K, L, M, N and P. The table shows the lengths, in km, of the direct roads. A dash means there is no direct road.
DKLMNP
D––32362639
K––42402947
L3242–913–
M36409–118
N26291311––
P3947–8––
(a) Find the least distances from D to K, from L to P and from N to P, stating each route.
[3]
On each trip the van leaves D, visits each village once and returns to D. Use the table of least distances.
(b) Starting at D, apply the nearest neighbour algorithm. Write down the order of the villages and the upper bound this gives for the length of a trip.
[3]
(c) Delete D. Use Prim's algorithm, starting at K, to find a minimum spanning tree of the five villages, listing the edges in order, and hence find a lower bound for the length of a trip.
[4]
(d) Explain why no trip uses exactly the edges of your lower bound.
[1]
The bounds found from the other vertices are: lower bounds K 123, L 96, M 102, N 113, P 100; upper bounds K 152, L 159, M 159, N 152, P 158.
(e) Write down the best inequality for the length L km of the shortest trip.
[2]
(f) The van averages 48 km per hour and stops for 25 minutes in each village. Fuel costs EUR 0.31 per km and the driver is paid EUR 21 per hour. Find the least and greatest possible costs of a trip given by your inequality.
[4]
(g) The driver tries the trip D, L, M, P, K, N, D. Find its length and comment.
[1]
Show solutionHide solution
(a) D, N, K =26+29=55; L, M, P =9+8=17; N, M, P =11+8=19.
M1A1A1
(b) D, N (26), M (11), P (8), L (17), K (42), then back to D (55).
M1A1
26+11+8+17+42+55=159 km.
A1
(c) KN 29, NM 11, MP 8, ML 9.
M1A1
The tree weighs 57, and the two shortest edges at D are DN 26 and DL 32.
M1
Lower bound 57+26+32=115 km.
A1
(d) M has degree 3 in these edges (NM, MP, ML), and a trip needs degree 2 at every village.
R1
(e) The largest lower bound is 123 (K) and the smallest upper bound is 152 (K and N).
M1
123\le L\le152.
A1
(f) Time =\dfrac{L}{48}+\dfrac{5\times25}{60} hours and cost =0.31L+21\left(\dfrac{L}{48}+\dfrac{125}{60}\right).
M1M1
L=123: EUR 135.69.
A1
L=152: EUR 157.37.
A1
(g) 32+9+8+47+29+26=151 km: inside the interval and shorter than the nearest neighbour trip.
R1

Final answer

(a) 55, 17, 19. (b) D, N, M, P, L, K, D; 159 km. (c) 115 km. (d) M has degree 3. (e) 123\le L\le152. (f) EUR 135.69 to EUR 157.37. (g) 151 km, inside the interval and shorter than 159 km.

Going further

Beyond the syllabus: the worked examples and investigations of the chapter's Going further pages.

G1 Two bounds from one tree

G1 Worked

[7 marks]
Use the table of least distances for Tariq's five farms in Section 12.7.
(a) Find a minimum spanning tree of all five farms and its total length.
[3]
(b) Explain why twice this length is an upper bound for the length of a round trip through all five farms, and write it down.
[2]
(c) Explain why the tree length is below the length of every round trip, and compare your bounds with 47\le L\le54 from Section 12.8.
[2]
Show solutionHide solution
(a) Kruskal accepts QR 6, ST 7, PR 9 and QT 11 (M1 A1), a total of 6+7+9+11=33 (A1). (b) Going along each tree edge out and back is a closed walk through every farm of length 66 (R1), and a repeated farm can be skipped using a least distance, so L\le66 (A1). (c) Removing one edge from a round trip leaves a spanning tree, so the round trip is longer than 33 (R1). The interval 33<L\le66 is much wider than 47\le L\le54, so the deleted-vertex and nearest-neighbour bounds are sharper (A1).

Final answer

QR, ST, PR, QT with length 33; L\le66; 33<L\le66 is wider than 47\le L\le54.

G2 Neighbour joins

G2 Worked

[5 marks]
In the solar park of Investigation G3, the hut is H(0, 0), and inverters are at A(3, 4) and B(9, 4), in hundreds of metres.
(a) Show that A lies inside the circle with diameter HB.
[3]
(b) Explain why the cable HB is never part of a minimum spanning tree of the six points.
[2]
Show solutionHide solution
(a) HB has length \sqrt{9^2+4^2}=\sqrt{97}, so the circle has centre (4.5,2) and radius \frac{\sqrt{97}}{2}=4.92 (M1 A1). The distance from A to the centre is \sqrt{1.5^2+2^2}=2.5<4.92 (A1). (b) HA =5 and AB =6 are both less than HB =9.85 (R1), so H, A and B are already joined by shorter cables when HB is considered, and Kruskal rejects HB (R1).

Final answer

Shown; HA and AB are shorter than HB, so Kruskal rejects HB.

G3 Investigation

[18 marks]
A solar park has a control hut H and five inverters A to E. Their positions, in hundreds of metres, are H(0, 0), A(3, 4), B(9, 4), C(12, 0), D(6, -4) and E(6, 1). Cables run in straight lines between these points.
(a) Show that the distance AE is \sqrt{18} and find the distance HE.
[2]
The other distances, in hundreds of metres, are HA 5, HB 9.85, HC 12, HD 7.21, AB 6, AC 9.85, AD 8.54, BC 5, BD 8.54, BE 4.24, CD 7.21, CE 6.08 and DE 5.
(b) Use Kruskal's algorithm to find the minimum total length of cable that joins all six points.
[3]
(c) Explain why twice your answer to (b) is an upper bound for the length of a walk that starts at H, visits every inverter and returns to H, and write down this bound.
[2]
(d) Starting at H, apply the nearest neighbour algorithm to find a better upper bound.
[3]
(e) By deleting E, find a lower bound for the length of such a walk.
[3]
(f) Write down an inequality for the shortest length L of the walk, and comment on how close the bounds are.
[2]
(g) Explain why removing one vertex from any closed walk through every point leaves a path that weighs at least as much as a minimum spanning tree of the remaining points, and hence why the method in (e) always gives a lower bound.
[3]
Show solutionHide solution
(a) AE=\sqrt{3^2+3^2}=\sqrt{18}=4.24 (M1), and HE=\sqrt{6^2+1^2}=\sqrt{37}=6.08 hundred metres (A1). (b) Kruskal accepts AE 4.24, BE 4.24, HA 5, BC 5 and DE 5 (M1 A1), and rejects AB 6 because it closes a cycle. The total is 15+6\sqrt2=23.5, which is 2350 m (A1). (c) Going out and back along each tree edge is a closed walk through every point (R1), and 2\times23.485=47.0, which is 4700 m (A1). (d) H, A (5), E (4.24), B (4.24), C (5), D (7.21), then back to H (7.21) (M1 A1), a total of 32.9, which is 3290 m (A1). (e) Without E, the tree HA 5, BC 5, AB 6 and then HD or CD at 7.21 (a tie) weighs 23.21 (M1 A1). Adding AE and BE, 4.24 each, gives 31.7, which is 3170 m (A1). (f) 31.7\le L\le32.9 (A1). The bounds are within about 4% of each other, so the tour is known closely (R1). (g) Removing one vertex from a closed walk leaves a path through all the other points, which is a spanning tree of them, so its weight is at least the minimum spanning tree (R1 R1). The two removed edges weigh at least the two shortest edges at the deleted point, so the sum is at least the bound in (e) (R1).

Final answer

\sqrt{18}, 6.08; 23.5; 47.0; 32.9; 31.7; 31.7\le L\le32.9, within about 4%; explained.

From the book

Photon Guidebook: Mathematics Applications and Interpretation HL for the IB Diploma

Chapter 12 teaches graph theory from the basics to full exam questions: how the IB asks it, every question type with a marked example, and these practice questions in three steps.

About the book

Questions © 2026 Photon Academy IB Tuition. Original IB-style questions; not IB past-paper questions. This site is independent and not endorsed by the IB.