Odd-Vertex Pairing for the Undirected Chinese Postman

From Edge Duplication to Pairing

An undirected postman route must be a closed walk that traverses every edge at least once. If the graph already has an Euler circuit, no edge needs to be repeated. Otherwise, some edge traversals must be added so that the resulting multigraph has even degree at every vertex. The key question is how to add them as cheaply as possible.

Assume throughout that \(G=(V,E)\) is a finite, connected, undirected simple graph with at least one edge, and that each edge \(e\) has a positive traversal cost \(c(e)\). A route’s cost is the sum of the costs of all its traversals, counting repeated traversals each time. The original edges must each be traversed at least once. Write \(O\) for the set of vertices of odd degree in \(G\).

The handshake lemma implies that \(|O|\) is even, so such pairings exist, including the empty pairing when \(O=\varnothing\). Because \(G\) is finite and connected, a shortest path exists between every pair of vertices. The costs used in a pairing are therefore distances through the graph, not necessarily costs of single edges.

Why the Pairing Gives the Optimum

We use the Euler-circuit characterization established in the earlier material: a connected undirected multigraph has an Euler circuit if and only if every vertex has even degree. The duplicated paths turn the original graph into a connected multigraph, since the original graph is connected and adding edge copies cannot disconnect it.

Proof. First choose any perfect matching of \(O\), and for each pair choose a shortest path in \(G\). Duplicate every edge once for each time it occurs in these paths. Consider a vertex \(v\). A path contributes an even number of incident edge copies at any internal vertex, and an odd number at each of its two endpoints. Since each odd vertex is an endpoint of exactly one chosen pair, the total number of added incidences at \(v\) is odd exactly when \(v\in O\). Thus a vertex that originally had odd degree receives an odd number of added incidences, and a vertex that originally had even degree receives an even number. In both cases its degree in the augmented multigraph is even. The multigraph is connected, so it has an Euler circuit. That circuit traverses every original edge and has additional cost equal to the matching cost. Taking a minimum-cost matching shows that the least additional cost is at most the minimum matching cost.

For the reverse inequality, take any closed postman route and count its traversals of each edge. For every original edge, at least one traversal is required. Regard one traversal as the original edge and all further traversals as added copies. The resulting multigraph has even degree at every vertex because the route is closed. Consequently, the added copies have odd degree exactly at the vertices in \(O\): adding degrees modulo \(2\), an originally odd degree needs an odd added degree to become even, while an originally even degree needs an even added degree.

Consider the multigraph consisting only of the added copies. In any connected component containing added edges, the number of its odd-degree vertices is even, by the handshake lemma. If that number is positive, add one new vertex and join it by one new edge to each odd-degree vertex of the component. The enlarged component is connected and every degree is even. Its Euler circuit, with the new edges removed, separates the added edges into trails whose endpoints are paired odd-degree vertices: each time the circuit passes through the new vertex, the segment between consecutive new edges is a trail in the added-edge component. Components with no odd-degree vertices need no pairing; their added-edge costs are nonnegative.

Each trail between a paired pair \(u,v\) has cost at least the shortest-path distance from \(u\) to \(v\) in \(G\). Indeed, a trail in the added copies is also a walk using edges of \(G\), and removing repeated portions cannot produce a path of greater cost because all edge costs are positive. The trails therefore give a perfect matching of \(O\) whose cost is at most the total cost of all added copies. The minimum matching cost is no larger than that route’s additional cost. This holds for every postman route, so the minimum matching cost is at most the least additional cost. Combining the two inequalities proves equality. \(\square\)

If \(O=\varnothing\), the matching is empty and has cost zero. The original graph is connected and all its degrees are even, so it already has an Euler circuit. Thus the result also covers this case.

Worked Examples

Using the Method

The pairing calculation determines the least additional cost; it does not mean that each matched pair must be connected by a single edge. A shortest path may contain several edges, and different chosen paths may use the same edge. If an edge occurs in more than one chosen path, duplicate it once for each occurrence: the argument counts added traversals with multiplicity.

Common Pitfall: Using Direct Edge Costs

In the star example, the leaves \(b,c\) are not adjacent. Treating their pair cost as unavailable because there is no direct edge would incorrectly rule out a perfect matching. Their correct pair cost is the shortest-path cost \(d(b,c)=1+1=2\), using the path through \(o\). The matching \(\{o,a\},\{b,c\}\) then has total cost \(1+2=3\).

Another error is to pair only vertices whose original edge is already present. The theorem concerns shortest paths between every pair of odd vertices in the connected graph. It is the paths’ traversal costs, not just the costs of existing direct edges between odd vertices, that determine the optimal duplication.