Skip to main content
MathidiaMathematics Academy
Discrete mathematics
Lesson 62 of 75
Easy practice

Route inspection

Objective. Find efficient traversals and pair odd vertices.

  1. 1. Learn
  2. 2. Worked example
  3. 3. Practice
  4. 4. Feedback
  5. 5. Continue

Learn: the key idea

The route inspection (Chinese postman) problem finds the shortest route that traverses every edge of a graph at least once and returns to the start. If every vertex has even degree, an Eulerian circuit exists and the minimum route length equals the sum of all edge weights; if some vertices have odd degree, the shortest routes between pairs of odd vertices must be added (duplicated) to make all degrees even, with the minimum extra distance chosen from pairing options. For example, a graph with exactly two odd vertices requires duplicating the shortest path between just that one pair.

Worked example

A network has total edge weight 40 and exactly two odd-degree vertices, with shortest path between them equal to 6. Use route inspection to find the minimum length of a route that traverses every edge and returns to the start.

40 … 6
Illustrated card showing 40 … 6
  1. 1Total edge weight of the graph is 40
  2. 2Since there are exactly two odd vertices, their shortest connecting path must be duplicated
  3. 3The shortest path between the two odd vertices is 6, so this is added once more
  4. 4Minimum route length = 40 + 6 = 46

Answer: 46

Concept mastery

Based on your past attempts at this lesson — the question types to practise again come first.

Complete a practice set to see your concept breakdown here.

Practice

Practice happens on its own screen, one question at a time. Answers stay hidden until you submit yours, and you can stop and pick up at the same question later.

Start practising

Common mistake. Students duplicate edges arbitrarily rather than finding the minimum-weight pairing of odd-degree vertices, which can give a route longer than necessary. Always identify all odd vertices first, then compare all possible pairings to minimise total duplicated weight.

Your progress

Tick each step as you finish it. Your exact reading position is saved automatically, so Continue drops you back on the same line.

0 of 5 steps complete

Your place saves automatically as you read.

My dashboard