In simple terms
A friendly intro before the formal notes — no formulas yet.
Networks Done Three Ways
A weighted graph is a set of places (vertices) joined by routes (edges) that each carry a cost. This topic answers three different network questions with three different algorithms: connect everything cheaply, cover every road, or visit every place. The trick is spotting which question you are being asked, then following the matching recipe carefully.
Picture a small town on a map. If a broadband company wants to lay cable so every house is connected using the least cable, it wants a minimum spanning tree — the skeleton that joins everyone with no wasteful loops. If a gritting lorry must drive down every street and return to the depot, that is the Chinese postman problem — cover every edge, and repeat as few streets as you can. If a delivery driver must call at every house once and come home, that is the travelling salesman problem — visit every vertex, shortest loop wins. Same map, three jobs, three methods.
- 1
Read the question and classify it. Connect all points with no loops means spanning tree; cover all roads means Chinese postman; visit all places once means travelling salesman.
- 2
Gather the graph data. Note the weight on each edge and, for the postman, the degree (number of edges) at each vertex.
- 3
Run the matching algorithm carefully, keeping ordered working: Kruskal's or Prim's for the tree, odd-vertex pairing for the postman, nearest-neighbour and deleted-vertex bounds for the salesman.
- 4
State the answer in context with its total weight, and for the travelling salesman quote the interval lower bound to upper bound.
Explore the concept
Use the live diagram and synced steps — play it or tap a step card to walk through.
Full topic notes
Formal explanation with the rigour you need for the exam.
Minimum spanning trees: Kruskal's algorithm
Suppose you must connect several locations with cable, pipe or road, and you want every location joined using the least total length, with no wasteful loops. The solution is a minimum spanning tree (MST): a subgraph that reaches all vertices, uses exactly edges and contains no cycle, chosen so the sum of its edge weights is as small as possible. Kruskal's algorithm builds it by being greedy about individual edges.
Goal: connect all vertices with the smallest total edge weight, using edges and no cycle.
Step 1: list every edge in increasing order of weight.
Step 2: add the cheapest edge.
Step 3: keep adding the next-cheapest edge, but reject any edge that would create a cycle with edges already chosen.
Step 4: stop once edges are in the tree. Their total weight is the weight of the MST.
The same tree, Prim's way
Prim's algorithm reaches the identical minimum spanning tree but grows it differently. Instead of sorting all edges and worrying about cycles, it keeps one connected tree and repeatedly reaches out to the nearest new vertex. Because the tree is always connected, a new edge can only create a cycle if it joins two vertices already inside — and Prim's never picks such an edge, so no separate cycle check is needed. This makes Prim's especially natural when the graph is given as a distance matrix.
Step 1: choose any starting vertex; it is the initial tree.
Step 2: find the cheapest edge from a vertex in the tree to a vertex not yet in the tree, and add that edge and vertex.
Step 3: repeat Step 2 until all vertices are in the tree.
No cycle check needed: you only ever connect a new (outside) vertex, so a cycle can never form.
The Chinese postman (route inspection) problem
The Chinese postman problem — also called route inspection — asks for the shortest closed walk that travels along every edge of a graph at least once and returns to the start. This is the problem of a postal worker, a gritting lorry, a street cleaner or a road inspector. Whether any edges must be repeated depends on the degrees of the vertices.
Goal: shortest closed route covering every edge at least once.
If every vertex has even degree the graph has an Eulerian circuit, so no edge need be repeated: the route length is just the sum of all edge weights.
If some vertices have odd degree (always an even number of them) some edges must be repeated. To find the least extra distance:
- List the odd-degree vertices.
- Consider every way to pair them up; for each pairing add the shortest-path distances between the paired vertices.
- Take the pairing with the smallest total.
- Route length = (sum of all edge weights) + (that minimum pairing total).
The travelling salesman problem (TSP)
The travelling salesman problem asks for the shortest closed tour that visits every vertex exactly once and returns to the start — a minimum-weight Hamiltonian cycle. Unlike the spanning tree and the postman, there is no efficient method guaranteed to find the exact optimum: the number of tours grows factorially, so for anything but tiny graphs we settle for trapping the answer. We find an upper bound (a real tour, so the optimum is no worse) and a lower bound (a value the optimum cannot fall below). At this level the graph is usually a complete graph given by a distance table.
Goal: shortest tour visiting every vertex once and returning to the start.
Upper bound — nearest-neighbour algorithm:
- Start at a chosen vertex.
- Travel to the nearest unvisited vertex.
- Repeat until all vertices are visited.
- Return directly to the start. The total is an upper bound.
Lower bound — deleted-vertex method:
- Delete a chosen vertex and all its edges.
- Find the MST of the remaining graph.
- Add the two shortest edges that were attached to the deleted vertex.
- The sum is a lower bound.
Conclusion: the optimal tour length satisfies lower bound upper bound.
Choosing the right algorithm
Half the marks in this topic are won by classifying the problem correctly before you compute. A spanning tree joins every vertex with no loops and is about the cheapest connection. The Chinese postman covers every edge and returns home. The travelling salesman visits every vertex once and returns home. Confusing the postman and the salesman is the most common and most expensive error, because the whole method changes.
Connect all points, least total, no loops → minimum spanning tree (Kruskal's or Prim's).
Cover every road / edge, return to start → Chinese postman (pair odd-degree vertices).
Visit every place / vertex once, return to start → travelling salesman (nearest-neighbour upper bound, deleted-vertex lower bound).
Spanning tree uses edges; a tour uses edges (it must close the loop).
Common mistakes examiners penalise
Adding one edge too many (or too few) to an MST — a spanning tree on vertices has exactly edges and no cycle. Adding a -th edge always closes a loop; stopping early leaves a vertex disconnected.
Skipping the cycle check in Kruskal's — you must reject the cheapest edge if it closes a loop, and show that rejection. Blindly taking the cheapest edges can give a graph with a cycle and a missing vertex.
Confusing the postman with the salesman — the postman covers every EDGE, the salesman visits every VERTEX. Choosing the wrong one loses the whole question.
Pairing odd vertices with direct edges instead of shortest paths — in the Chinese postman you repeat the shortest PATH between an odd pair, which may run through other vertices, not necessarily the single connecting edge.
Treating the nearest-neighbour tour as the exact answer — it is only an upper bound; it is a valid tour but usually not the shortest.
Adding the two longest deleted edges for the lower bound — you add the two SHORTEST edges at the deleted vertex to the MST of the rest; using the longest destroys the bound.
Forgetting to return to the start — both the postman route and the salesman tour are closed: the salesman tour therefore has edges, not . Omitting the final edge back to the start undercounts.
Reporting the wrong direction of the interval — the optimal TSP length lies between the lower and upper bounds; quote it as lower upper, not the reverse.
Where this leads
These three algorithms are your introduction to discrete optimisation, the branch of mathematics behind route planning, network design and scheduling. The greedy idea that powers Kruskal's and nearest neighbour reappears whenever a problem is solved one locally best step at a time; the bounding idea behind the TSP — trapping an answer you cannot compute exactly between something achievable and something unbeatable — is a habit of mind used throughout applied mathematics and computer science. Master the classification first, then the mechanics, and always show the ordered working: the method marks and follow-through are what protect your score when a single weight slips.
Worked examples
See the formulas applied — reveal one step at a time, like the exam.
A weighted graph on vertices A–E has edges AB 4, AC 3, BC 2, BD 5, CD 6, DE 4, CE 7. Use Kruskal's algorithm to find the minimum spanning tree and its total weight. [5]
- 1
There are vertices, so a spanning tree needs edges.\n\nStep 1: sort the edges by weight.\nBC (2), AC (3), AB (4), DE (4), BD (5), CD (6), CE (7).\n\nStep 2: add edges cheapest first, rejecting any that make a cycle.\n\n| Edge | Weight | Decision | Reason |\n|---|---|---|---|\n| BC | 2 | Accept | connects B and C |\n| AC | 3 | Accept | connects A |\n| AB | 4 | Reject | would close cycle A–B–C–A |\n| DE | 4 | Accept | connects D and E |\n| BD | 5 | Accept | connects the D–E part to the rest |\n\nAfter accepting BC, AC, DE, BD we have 4 edges joining all five vertices, so we stop. (CD and CE are never needed.)\n\nMinimum spanning tree: edges BC, AC, BD, DE.\n\nTotal weight:
Using the same graph (edges AB 4, AC 3, BC 2, BD 5, CD 6, DE 4, CE 7), apply Prim's algorithm starting from vertex A to find the minimum spanning tree and confirm its weight. [5]
- 1
Begin with the tree containing only A.\n\nStep 1: from {A}. Edges leaving A: AC (3), AB (4). Cheapest is AC (3). Add C. Tree = {A, C}. [M1: choose cheapest edge to a new vertex]\n\nStep 2: from {A, C}. Edges to outside vertices: AB (4), BC (2), CD (6), CE (7). Cheapest is BC (2). Add B. Tree = {A, B, C}. [A1]\n\nStep 3: from {A, B, C}. Edges to outside vertices: BD (5), CD (6), CE (7). Cheapest is BD (5). Add D. Tree = {A, B, C, D}. [A1]\n\nStep 4: from {A, B, C, D}. Edges to the last vertex E: DE (4), CE (7). Cheapest is DE (4). Add E. Tree = {A, B, C, D, E}. [M1: continue until all vertices joined]\n\nAll five vertices are connected using edges AC, BC, BD, DE.\n\nTotal weight: [A1]\n\nThis is the same tree and the same total weight, 14, that Kruskal's produced — a useful check that both algorithms agree.
A groundskeeper must walk along every path in a park and return to the gate. The paths and their lengths (in hundreds of metres) are AB 8, AC 5, BC 4, BD 7, CD 9, CE 6, DE 3. Find the length of the shortest inspection route. [6]
- 1
Step 1: total of all edge weights.\n [A1]\n\nStep 2: find the degree of each vertex.\n- deg(A) = 2 (edges AB, AC) — even\n- deg(B) = 3 (edges AB, BC, BD) — odd\n- deg(C) = 4 (edges AC, BC, CD, CE) — even\n- deg(D) = 3 (edges BD, CD, DE) — odd\n- deg(E) = 2 (edges CE, DE) — even\nThe odd-degree vertices are B and D. [M1]\n\nStep 3: shortest path between the odd pair B and D.\n- Direct BD: .\n- B–C–D: .\n- B–C–E–D: .\nThe shortest B-to-D distance is the direct edge, . [M1]\nWith only two odd vertices there is a single pairing, so this is the least extra distance. [A1]\n\nStep 4: route length.\n [M1]\n\nAnswer: the shortest inspection route is metres. [A1]
A courier starts at depot A, must visit branches B, C, D and E once each, and return to A. The table gives the shortest travel times (minutes) between them.\n\n| | A | B | C | D | E |\n|---|---|---|---|---|---|\n| A | – | 12 | 20 | 15 | 25 |\n| B | 12 | – | 10 | 18 | 14 |\n| C | 20 | 10 | – | 11 | 16 |\n| D | 15 | 18 | 11 | – | 13 |\n| E | 25 | 14 | 16 | 13 | – |\n\n(a) Use the nearest-neighbour algorithm from A to find an upper bound. \n(b) By deleting vertex A, find a lower bound. [8]
- 1
(a) Upper bound — nearest neighbour from A.\n- At A, nearest is B (12). Go to B. [M1: start and move to nearest]\n- At B, unvisited nearest is C (10). Go to C.\n- At C, unvisited nearest is D (11). Go to D.\n- At D, only E is left (13). Go to E.\n- Return E → A (25) to close the tour. [M1: complete the tour back to A]\nTour: A → B → C → D → E → A.\nLength minutes. So an upper bound is . [A1]\n\n**(b) Lower bound — delete A.\nRemove A and its edges, leaving vertices B, C, D, E. [M1]\nFind the MST of {B, C, D, E}. Edges in order: BC (10), CD (11), DE (13), BE (14), CE (16), BD (18).\n- Accept BC (10).\n- Accept CD (11).\n- Accept DE (13). That is edges connecting all four vertices; stop.\nMST weight . [A1]\nAdd the two shortest edges from the deleted vertex A: from AB (12), AC (20), AD (15), AE (25) the two smallest are AB (12) and AD (15). [M1]\nLower bound minutes. [A1]\n\nConclusion:** the optimal tour time satisfies minutes.
How it all connects
The big idea sits in the middle — tap a linked idea to explore the link.
Tap a linked idea to see how it connects back to the main topic — that connection is what examiners reward.
Glossary
Try to recall each definition before you reveal it.
Quick check
Answer in your head first — then tap to check. No pressure.
Revision flashcards
Flip the card. Test yourself before the exam.
Spanning tree
A subgraph that connects all vertices of a graph using exactly edges and contains no cycle. Every vertex is reachable, and there are no wasteful loops.
Key takeaways
Review these before you close the topic — retrieval beats re-reading.
- ✓
Goal: connect all vertices with the smallest total edge weight, using edges and no cycle.
- ✓
Step 1: list every edge in increasing order of weight.
- ✓
Step 2: add the cheapest edge.
- ✓
Step 3: keep adding the next-cheapest edge, but reject any edge that would create a cycle with edges already chosen.
- ✓
Step 4: stop once edges are in the tree. Their total weight is the weight of the MST.
Practice — then mark it
The whole point: a real Cambridge question, marked mark-by-mark.
Get a Paper 2 network question marked: build the MST, pair the odd vertices, or bound the tour with full working
Get a Paper 2 network question marked: build the MST, pair the odd vertices, or bound the tour with full working
Extra simulations & links
PhET, GeoGebra and other curated tools — open in a new tab.
Frequently asked
Checkpoint
One marked question is worth ten re-reads — close the loop before you move on.
Reading it isn’t knowing it — prove it.
Before you move on: do Get a Paper 2 network question marked: build the MST, pair the odd vertices, or bound the tour with full working on paper, snap a photo, and get examiner-style feedback on exactly where you win and lose marks.