Undirected Chinese Postman

The Undirected Chinese Postman Problem asks for the minimum cost closed walk that visits every edge of an undirected graph at least once. If the graph is Eulerian (every vertex has an even degree) and connected, the Eulerian circuit itself is the optimal walk, and its cost is simply the sum of all edge weights. If there are vertices with odd degrees, we must traverse some edges more than once. We do this by finding a minimum-weight perfect matching among the odd-degree vertices and duplicating the paths between matched pairs.

Worked Example

Consider a simple path graph with 4 vertices: 0 - 1 - 2 - 3 with edge weights 1, 2, 1 respectively.

Original cost: 1 + 2 + 1 = 4.
Odd degree vertices: 0 and 3.
Shortest path distance between 0 and 3 is 1 + 2 + 1 = 4.
The added traversal cost is 4.
Optimal closed cost: 4 + 4 = 8.

Original Cost: 4\n Odd vertices: [0, 3]\n Added cost: 4\n Optimal: 8

Experiment

In the interactive module, you can explore various preset graphs using the Graph control. Observe how the number of odd-degree vertices impacts the matching and the total added cost.

Select Square tail from the Graph control to see a graph with 2 odd vertices. Note the matched odd pairs and the added traversal cost.
Select Star from the Graph control to see a graph with 4 odd vertices. Observe the red dashed curves indicating the duplicate traversals forming the minimum perfect matching.

Limitations

This implementation uses a bitmask dynamic programming approach (O(V² 2^V)) to find the minimum perfect matching, which is feasible only for graphs with a very small number of odd vertices (typically up to 15-20). For larger instances, Edmond's Blossom algorithm in O(V³) is required. Disconnected graphs without a single Eulerian component are explicitly marked as unavailable, as they do not possess a single route.

References

For more information, consider reading the following classical references:

Undirected Chinese Postman