# Graph theory applications: CPP and TSP

> IB Mathematics AI HL · IB Math AI HL
> Source: https://www.owlsprep.com/study/ib-math-ai-hl-u5-graph-theory-applications-cpp-and/

This module covers two key optimization applications of graph theory: the Chinese Postman Problem (CPP) for route planning that covers every edge, and the Travelling Salesman Problem (TSP) for visiting every vertex. We cover exam-relevant solution methods and common pitfalls.

**Prerequisites:** [Basic graph theory terminology and properties](https://www.owlsprep.com/study/ib-math-ai-hl-u5-introduction-to-graph-theory/); [Minimum spanning tree algorithms](https://www.owlsprep.com/study/ib-math-ai-hl-u5-minimum-spanning-trees/)

## Learning objectives

- Distinguish between the Chinese Postman Problem (CPP) and Travelling Salesman Problem (TSP)
- Solve CPP for connected graphs with 0 or 2 odd-degree vertices
- Calculate upper and lower bounds for TSP using standard IB methods
- Interpret CPP and TSP solutions in real-world optimization contexts

## The Chinese Postman Problem (CPP)

**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.

1. If **0 odd vertices**: The graph is Eulerian, the optimal route is the Eulerian circuit, total weight = sum of all edge weights.
2. 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.
3. 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).

**Worked example:** 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. $$\text{Total optimal length} = 22 + 5 = 27$$

> **Exam tip:** Always check the degree of every vertex first before solving a CPP problem; miscounting odd vertices is the most common early error.

*Calculator:* allowed

## Introduction to the Travelling Salesman Problem (TSP)

**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**

Check your understanding of the difference between CPP and TSP:

1. Which problem requires traversing every edge at least once?

   - CPP
   - TSP

   *Answer:* CPP

   *Why:* Correct! CPP's core requirement is to cover all edges, while TSP covers all vertices.

2. Which problem requires visiting every vertex exactly once (except the start/end)?

   - CPP
   - TSP

   *Answer:* TSP

   *Why:* Correct! TSP requires visiting each vertex once, while CPP can repeat vertices.

*Calculator:* allowed

## Finding TSP Upper Bounds

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:

1. Start at the specified starting vertex (given in the exam question)
2. Move to the unvisited vertex with the smallest edge weight from your current vertex
3. Repeat until all vertices are visited
4. Add the weight of the edge from the last vertex back to the starting vertex to close the cycle

**Worked example:** Use the nearest neighbour algorithm starting at vertex A to find an upper bound for this symmetric TSP: edge weights are $AB=3$, $AC=6$, $AD=3$, $BC=5$, $BD=4$, $CD=2$.

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 + 2 = 5$.
3. Step 3: Current vertex C. Only unvisited vertex is B. Edge CB=5. Move to B. Total so far: $5 + 5 = 10$.
4. Step 4: All vertices visited. Return to A from B. Edge BA=3. Calculate total upper bound:
5. $$\text{Upper bound} = 10 + 3 = 13$$

> **tip**
>
> To find the best (smallest) upper bound, run the nearest neighbour algorithm starting from every vertex, then select the smallest resulting total. Always do this if the question asks for the best upper bound.

*Calculator:* allowed

## Finding TSP Lower Bounds

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):

1. Delete any one vertex from the original graph
2. Find the minimum spanning tree (MST) of the remaining graph
3. Add the weights of the two smallest distinct edges connected to the deleted vertex to the MST weight
4. The resulting total is your lower bound

**Worked example:** Find a lower bound for the TSP from the previous example (edge weights: $AB=3$, $AC=6$, $AD=3$, $BC=5$, $BD=4$, $CD=2$) 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 $2 + 4 = 6$.
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. $$\text{Lower bound} = 6 + 3 + 3 = 12$$

*Calculator:* allowed

## Common pitfalls

- **Wrong:** Confusing CPP and TSP requirements, solving CPP as if it needs to visit all vertices instead of all edges.
  - Why it fails: The two problems have fundamentally different core objectives, so mixing them gives an incorrect solution.
  - Correct: Always confirm the problem type first: CPP = cover every edge, TSP = visit every vertex.
- **Wrong:** For CPP with 2 odd vertices, forgetting to add the repeated path weight to the total sum of all edges.
  - Why it fails: Many students only report the weight of the repeated path instead of the full route weight.
  - Correct: Always add the weight of the repeated path to the sum of all original edge weights for CPP.
- **Wrong:** In the nearest neighbour algorithm for TSP, stopping after visiting all vertices and forgetting to add the return edge to the start.
  - Why it fails: TSP requires a closed cycle that returns to the starting vertex, so this step is required for full marks.
  - Correct: Always add the weight of the edge from the last vertex back to the start to get your total upper bound.
- **Wrong:** For TSP lower bounds, adding only one edge connected to the deleted vertex instead of two.
  - Why it fails: A TSP cycle must enter and exit the deleted vertex, so two distinct edges are required.
  - Correct: Always add the two smallest distinct edges connected to the deleted vertex when calculating the lower bound.

## 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 |

## 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.

---

From [OwlsPrep](https://www.owlsprep.com) — free study guides for A-Level, IB, AP and IGCSE, written against the official syllabus. Canonical page: https://www.owlsprep.com/study/ib-math-ai-hl-u5-graph-theory-applications-cpp-and/