The Chinese Postman Problem as Edge Duplication

From Street Inspection to an Euler Circuit

A postperson who must traverse every street and return to the starting point needs a closed route that covers every edge. A graph may have vertices of odd degree, so traversing each edge exactly once may not be possible. The central idea of the undirected Chinese postman problem is to allow repeated traversals: take the original graph, add copies of some edges, and seek a closed route that uses every original edge. If the added copies make all vertex degrees even, the resulting connected multigraph has an Euler circuit, which supplies the route.

Throughout, graphs are finite and undirected. The original graph is simple, connected, and has at least one edge. Each edge \(e\) has a strictly positive cost \(c(e)\), such as its length or the time needed to traverse it. When edges are duplicated, each added copy has the same cost as the original edge. Copies are regarded as distinct edges when counting degrees and describing a route.

The route is a walk, not necessarily a trail: it may use an edge more than once. A trail does not repeat edges, while a walk can. If a route repeats an edge, we can represent each extra traversal by an added copy of that edge. The route then traverses each edge of the resulting multigraph exactly once. That is why the problem can be formulated using Euler circuits.

How Duplicating a Path Changes Parity

Degree parity controls whether an undirected graph has an Euler circuit. Duplicating a path gives a direct way to adjust that parity. A path here has no repeated vertices; its edges are added as copies, one copy of each edge on the path.

Proof. The duplicated path adds one new incident edge at each endpoint, so the degree at each endpoint rises by \(1\). Every internal vertex of the path is incident with two of its edges, and receives one copy of each; its degree rises by \(2\). Since adding \(1\) changes parity and adding \(2\) does not, exactly the endpoint parities change. \(\square\)

This also explains the role of the path’s endpoints. If both are odd-degree vertices, duplicating the path makes them even; internal vertices keep their parity. If paths are chosen so that every odd-degree vertex is an endpoint exactly once, all degrees become even. Such paths exist between any chosen pair of vertices because the original graph is connected. The number of odd-degree vertices is even: the sum of all degrees is \(2|E(G)|\), since each edge contributes one to the degree at each of its two ends.

An Exact Edge-Copy Formulation

For each original edge \(e\), let \(z_e\) be the number of extra copies added. The total number of copies of \(e\) in the augmented graph is \(1+z_e\): one original edge plus the added copies. The degree at a vertex \(v\) in that multigraph is therefore \(\deg_G(v)+\sum_{e\ni v}z_e\). To make it even, the added copies incident with \(v\) must have the same parity as \(\deg_G(v)\).

Proof. First take any closed edge-covering route. For each edge \(e\), let \(z_e\) count how many times the route traverses \(e\) beyond its required first traversal. Then \(z_e\) is a nonnegative integer, and the route cost is \(\sum_{e\in E(G)}c(e)+\sum_{e\in E(G)}c(e)z_e\).

Count the route’s traversals as edges in a multigraph, distinguishing repeated traversals as copies. At each vertex, the number of arrivals equals the number of departures because the route is closed. Each arrival and departure uses an incident edge, so the degree in this traversal multigraph is even. That degree is \(\deg_G(v)+\sum_{e\ni v}z_e\). Hence the copy counts of any closed edge-covering route satisfy all the displayed parity conditions. The minimum over those counts is therefore no greater than the cost of any such route after subtracting the fixed original cost.

Conversely, take any nonnegative integer counts \(z_e\) satisfying the parity conditions and form the multigraph with those added copies. Its degrees are all even by the conditions. It is connected because it contains every edge of the connected original graph. By the Euler circuit characterization, a connected multigraph with all degrees even has an Euler circuit. That circuit traverses every original edge and every added copy once, so it gives a closed edge-covering route whose cost is exactly \(\sum_{e\in E(G)}c(e)+\sum_{e\in E(G)}c(e)z_e\).

There is at least one feasible choice of copy counts: pair the even number of odd-degree vertices and duplicate a path between the vertices in each pair. The lemma shows that this changes the parity at each paired endpoint and nowhere else. Finally, a minimum is attained. A feasible choice gives a finite upper bound on the extra cost; since every edge cost is strictly positive, only finitely many nonnegative integer vectors \(z\) can have extra cost at most that bound. The minimum over the feasible vectors within the bound exists, and no vector outside it can improve the cost. The two directions establish the formula. \(\square\)

The formula separates the unavoidable cost of covering the original edges from the extra cost caused by repeated traversals. It characterizes which edge-copy counts are valid, but it does not prescribe how to find the least-cost counts. In particular, the parity conditions alone do not say which paths should be duplicated when there are several odd-degree vertices.

Why the Formulation Matters—and a Common Pitfall

The edge-copy formulation converts a route problem into a degree-parity problem. Once the copies are chosen, the Euler circuit characterization guarantees a way to traverse the augmented edges as one closed route. This separates two questions: which copies make all degrees even, and how to order the resulting edges into a route. The first is the cost-selection problem; the second is supplied by an Euler circuit.

A common mistake is to report only the cost of the duplicated edges as the cost of the postperson’s route. In the path example, the duplicated copies cost \(3\), but the postperson must still traverse the original three edges, which cost \(3\). The route cost is \(3+3=6\), not \(3\). In general, the added-copy cost is only the extra cost above the unavoidable \(\sum_{e\in E(G)}c(e)\).

Another parity error is to say that every vertex on a duplicated path changes parity. The two endpoints gain one incident copy each and do change parity; an internal vertex gains two incident copies and keeps its parity. For instance, duplicating \(1,2,3,4\) in the first example changes the degrees by \(1,2,2,1\), not by \(1,1,1,1\). Checking degree increments this way helps verify that the chosen copies actually produce an Eulerian multigraph.