Graph theory applications: CPP and TSP
IB Mathematics AI HLΒ· Topic 5: Statistics and ProbabilityΒ· 30 min read
1. The Chinese Postman Problem (CPP)β β β ββHL onlyβ± 15 min
β Calculator OK
Chinese Postman Problem
The problem of finding the shortest closed walk that traverses every edge of an undirected connected graph at least once, starting and ending at the same vertex.
Example:
Planning a postal route that covers every street in a neighborhood, returning to the delivery depot.
CPP solutions depend on the number of odd-degree vertices in the graph. By Euler's handshaking lemma, any graph has an even number of odd vertices. IB AI HL only assesses CPP for graphs with 0 or 2 odd vertices.
If 0 odd vertices: The graph is Eulerian, the optimal route is the Eulerian circuit, total weight = sum of all edge weights.
If 2 odd vertices: The optimal route requires repeating the shortest path between the two odd vertices. Total weight = sum of all edges + weight of the repeated path.
If more than 2 odd vertices: Pair odd vertices and repeat shortest paths between pairs to get minimum added weight (not assessed in IB AI HL).
A connected graph has 4 vertices A, B, C, D with degrees: A(2 even), B(3 odd), C(2 even), D(1 odd). Sum of all edge weights is 22. The shortest path between B and D has total weight 5. Find the length of the optimal CPP route.
- 1
Step 1: Count the number of odd-degree vertices. There are 2 odd vertices: B and D.
- 2
Step 2: For 2 odd vertices, add the weight of the shortest path between them to the total sum of all edge weights:
- 3
Exam tip:
Always check the degree of every vertex first before solving a CPP problem; miscounting odd vertices is the most common early error.
2. Introduction to the Travelling Salesman Problem (TSP)β β β β βHL onlyβ± 20 min
β Calculator OK
Travelling Salesman Problem
An optimization problem that requires finding the Hamiltonian cycle of minimum total weight that visits every vertex of a graph exactly once and returns to the origin vertex.
Example:
Planning a delivery route that visits every city once before returning to the central warehouse.
Unlike CPP, there is no simple efficient algorithm to find the exact optimal TSP solution for large graphs. For IB AI HL, you will only be required to calculate upper and lower bounds for the optimal solution, rather than finding the exact value for most problems.
Check your understanding of the difference between CPP and TSP:
Which problem requires traversing every edge at least once?
CPP
TSP
Which problem requires visiting every vertex exactly once (except the start/end)?
CPP
TSP
Reveal answer
1 βCorrect! TSP requires visiting each vertex once, while CPP can repeat vertices.
3. Finding TSP Upper Boundsβ β β β βHL onlyβ± 20 min
β Calculator OK
An upper bound for TSP is a total weight that is guaranteed to be greater than or equal to the true optimal solution. The standard IB AI HL method to find an upper bound is the nearest neighbour algorithm:
Start at the specified starting vertex (given in the exam question)
Move to the unvisited vertex with the smallest edge weight from your current vertex
Repeat until all vertices are visited
Add the weight of the edge from the last vertex back to the starting vertex to close the cycle
Use the nearest neighbour algorithm starting at vertex A to find an upper bound for this symmetric TSP: edge weights are , , , , , .
- 1
Step 1: Start at A. Unvisited vertices are B, C, D. The smallest edges from A are AB=3 and AD=3; pick AD first. Total so far: 3.
- 2
Step 2: Current vertex D. Unvisited vertices are B, C. The smallest edge from D is CD=2. Move to C. Total so far: .
- 3
Step 3: Current vertex C. Only unvisited vertex is B. Edge CB=5. Move to B. Total so far: .
- 4
Step 4: All vertices visited. Return to A from B. Edge BA=3. Calculate total upper bound:
- 5
4. Finding TSP Lower Boundsβ β β β β HL onlyβ± 20 min
β Calculator OK
A lower bound for TSP is a value guaranteed to be less than or equal to the true optimal solution. The standard IB AI HL method uses minimum spanning trees (MST):
Delete any one vertex from the original graph
Find the minimum spanning tree (MST) of the remaining graph
Add the weights of the two smallest distinct edges connected to the deleted vertex to the MST weight
The resulting total is your lower bound
Find a lower bound for the TSP from the previous example (edge weights: , , , , , ) by deleting vertex A.
- 1
Step 1: Delete vertex A. Remaining vertices are B, C, D.
- 2
Step 2: Find the MST of the remaining graph. The MST uses edges CD=2 and BD=4, so total MST weight is .
- 3
Step 3: Get the two smallest edges connected to the deleted vertex A. The edges from A are AB=3, AD=3, AC=6, so the two smallest are 3 and 3.
- 4
Step 4: Calculate the total lower bound:
- 5
5. Common Pitfalls
Wrong move:
Confusing CPP and TSP requirements, solving CPP as if it needs to visit all vertices instead of all edges.
Why:
The two problems have fundamentally different core objectives, so mixing them gives an incorrect solution.
Correct move:
Always confirm the problem type first: CPP = cover every edge, TSP = visit every vertex.
Wrong move:
For CPP with 2 odd vertices, forgetting to add the repeated path weight to the total sum of all edges.
Why:
Many students only report the weight of the repeated path instead of the full route weight.
Correct move:
Always add the weight of the repeated path to the sum of all original edge weights for CPP.
Wrong move:
In the nearest neighbour algorithm for TSP, stopping after visiting all vertices and forgetting to add the return edge to the start.
Why:
TSP requires a closed cycle that returns to the starting vertex, so this step is required for full marks.
Correct move:
Always add the weight of the edge from the last vertex back to the start to get your total upper bound.
Wrong move:
For TSP lower bounds, adding only one edge connected to the deleted vertex instead of two.
Why:
A TSP cycle must enter and exit the deleted vertex, so two distinct edges are required.
Correct move:
Always add the two smallest distinct edges connected to the deleted vertex when calculating the lower bound.
6. Quick Reference Cheatsheet
Problem Type | Core Requirement | Key Solution Rule |
|---|---|---|
CPP (0 odd vertices) | Traverse all edges, return to start | Optimal = sum of all edge weights |
CPP (2 odd vertices) | Traverse all edges, return to start | Optimal = sum of edges + shortest path between odd vertices |
TSP Upper Bound | Visit all vertices, return to start | Nearest neighbour: start at given vertex, pick closest unvisited, add return edge |
TSP Lower Bound | Visit all vertices, return to start | Delete 1 vertex, find MST of remaining, add two smallest edges to deleted vertex |
When this came up on past exams
AI-estimated based on syllabus patterns β cross-check with official past papers for accuracy. Use only as revision-focus signals.
- 2025 Β· 2
CPP optimal route calculation
- 2023 Β· 2
TSP upper and lower bound calculation
- 2021 Β· 2
Real-world TSP logistics problem
Going deeper
What's Next
CPP and TSP are core optimization topics that frequently appear as extended response questions in IB AI HL Paper 2, and are widely used in real-world logistics, delivery route planning, and network design. Mastering these methods builds on your understanding of graph fundamentals and minimum spanning trees, and prepares you for more advanced network problems like critical path analysis for project management. These topics also provide a strong foundation for university studies in operations research, computer science, and data analytics.