The Undirected Postman Problem
A route inspector, street sweeper or delivery worker may need to traverse every edge of a network and return to the starting point. If the network does not already have an Euler circuit, some edges must be traversed more than once. The undirected Chinese postman problem asks for a closed route of minimum total weight that uses every edge at least once. The key choice is not to repeat edges arbitrarily: it is to connect the odd-degree vertices using paths of minimum total weight.
Throughout, the original network is a finite, connected, simple, undirected graph \(G=(V,E)\) with a positive weight \(w(e)\) on each edge. A route may repeat vertices and edges. Its weight is the sum of the weights of all edge traversals, counting repeated traversals each time. When we duplicate an edge, we add a separate copy with the same weight; the resulting graph may be a multigraph. We use the earlier Euler circuit characterization: a finite connected graph or multigraph has an Euler circuit exactly when every vertex has even degree.
Why Pairing Odd Vertices Is the Right Calculation
First, every finite graph has an even number of odd-degree vertices. This fact ensures that the odd vertices can be grouped into pairs.
Proof. Each edge contributes \(1\) to the degree of each of its two endpoints, so the sum of all vertex degrees is twice the number of edges and is even. A sum of integers is even only if it contains an even number of odd summands. Therefore the number of odd-degree vertices is even. \(\square\)
For a set \(T\) of even size, a pairing is a partition of \(T\) into two-element sets. The cost of a pairing is the sum of the shortest-path distances between the paired vertices, where path weight means the sum of its edge weights.
Proof. Consider any postman route. For each original edge, keep one required traversal and regard any additional traversals as copies. Let \(H\) be the multiset of these additional edge traversals. At every vertex, the total number of incident traversals in the closed route is even: each arrival is balanced by a departure. Consequently, the degree in \(H\) is odd exactly at the vertices that had odd degree in \(G\). In other words, the odd-degree vertices of \(H\) are exactly \(T\).
If \(T=\varnothing\), the route has nonnegative extra weight, so its weight is at least \(W\), as required. Now suppose \(T\ne\varnothing\). In the components of \(H\) that contain vertices of \(T\), add a new vertex \(z\) and one edge from \(z\) to each vertex of \(T\). Each vertex of \(T\) now has even degree; all other vertices in those components already had even degree. The degree of \(z\) is \(|T|\), which is even by the lemma. The augmented multigraph is connected on its non-isolated vertices: the added edges join all components of \(H\) that contain vertices of \(T\). By the Euler circuit characterization, it has an Euler circuit.
Removing \(z\) and its incident edges from that circuit splits it into trails in \(H\), each joining two vertices of \(T\). These trails pair the vertices of \(T\). For each pair, the shortest-path distance in \(G\) is no greater than the weight of its trail. Components of \(H\) containing no vertices of \(T\) have nonnegative weight and can be discarded for this comparison. Thus the cost of some pairing of \(T\) is at most the weight of \(H\), so the minimum pairing cost is at most the extra weight of any postman route.
Conversely, choose a minimum-cost pairing of \(T\), and for each pair duplicate the edges on a shortest path joining its vertices. At each paired endpoint the degree parity changes once; at every internal vertex of a path it changes an even number of times. Since each vertex of \(T\) occurs in exactly one pair, the augmented graph has even degree at every vertex. It remains connected because the original graph is connected and only edges of paths in \(G\) have been duplicated. The Euler circuit characterization therefore gives a closed route using every original edge and every duplicated copy. Its weight is \(W\) plus the pairing cost. The lower and upper bounds agree, proving the formula. \(\square\)
Work the Six-Vertex Graph
Worked Example: Find the Odd Vertices and Original Weight
Let \(G\) be the finite, simple, undirected graph with vertex set \(V=\{A,B,C,D,E,F\}\). Its edges have the following weights: \(AB,BC,CD,DE,EF,FA\) each have weight \(2\); \(AC\) has weight \(3\); and \(DF\) has weight \(1\). The six weight-\(2\) edges form a cycle, and \(AC\) and \(DF\) are chords.
The degrees count edges, not weights. Vertex \(A\) is incident with \(AB,FA,AC\), so \(\deg(A)=3\). Vertex \(B\) is incident with \(AB,BC\), so \(\deg(B)=2\). Vertex \(C\) is incident with \(BC,CD,AC\), so \(\deg(C)=3\). Vertex \(D\) is incident with \(CD,DE,DF\), so \(\deg(D)=3\). Vertex \(E\) is incident with \(DE,EF\), so \(\deg(E)=2\). Vertex \(F\) is incident with \(EF,FA,DF\), so \(\deg(F)=3\). Therefore the odd-vertex set is \(T=\{A,C,D,F\}\).
The cycle edges contribute \(6\cdot2=12\) to the total edge weight. The two chords contribute \(3+1=4\), so \(W=12+4=16\). As a check on the edge list, the degrees sum to \(3+2+3+3+2+3=16\), which equals \(2|E|=2\cdot8=16\).
Worked Example: Compare All Three Pairings
Use the graph just specified: \(V=\{A,B,C,D,E,F\}\), with weight-\(2\) edges \(AB,BC,CD,DE,EF,FA\), weight-\(3\) edge \(AC\), and weight-\(1\) edge \(DF\). The four odd vertices have three possible pairings. We first calculate the shortest-path distances needed for them.
For \(A\) and \(C\), the direct edge \(AC\) has weight \(3\), while the route \(A-B-C\) has weight \(2+2=4\); thus \(d(A,C)=3\). For \(A\) and \(D\), the route \(A-F-D\) has weight \(2+1=3\). The alternatives through \(C\), \(A-C-D\), have weight \(3+2=5\), and through \(B,C\), \(A-B-C-D\), have weight \(2+2+2=6\); hence \(d(A,D)=3\). The direct edge gives \(d(A,F)=2\).
The direct edge \(CD\) gives \(d(C,D)=2\). For \(C\) and \(F\), the route \(C-D-F\) has weight \(2+1=3\), which is shorter than \(C-A-F\), of weight \(3+2=5\); hence \(d(C,F)=3\). Finally, the direct edge \(DF\) gives \(d(D,F)=1\). The pairing costs are therefore:
- \(\{A,C\},\{D,F\}\): \(d(A,C)+d(D,F)=3+1=4\).
- \(\{A,D\},\{C,F\}\): \(d(A,D)+d(C,F)=3+3=6\).
- \(\{A,F\},\{C,D\}\): \(d(A,F)+d(C,D)=2+2=4\).
The minimum pairing cost is \(4\), attained by two pairings. By the theorem, the minimum postman-route weight is \(W+4=16+4=20\). This comparison checks all possible pairings, not just the first one found.
Construct and Check an Optimal Route
Worked Example: Duplicate Two Chords and Trace the Route
Use the same graph, explicitly given by \(V=\{A,B,C,D,E,F\}\) and weighted edges \(AB(2),BC(2),CD(2),DE(2),EF(2),FA(2),AC(3),DF(1)\). Choose the minimum pairing \(\{A,C\},\{D,F\}\). The shortest paths are the direct edges \(AC\) and \(DF\), so duplicate one copy of each. Every vertex now has even degree: \(A,C,D,F\) each gain one incident copy, changing their odd degrees to even, while \(B,E\) remain even.
An Euler circuit in the augmented multigraph gives the closed route \(A-B-C-A-C-D-F-D-E-F-A\), returning to its starting vertex. Its ten traversals, in order, are \(AB,BC,AC,AC',CD,DF,DF',DE,EF,FA\), where primes mark the duplicated copies. Their weights are \(2,2,3,3,2,1,1,2,2,2\). Thus the route weight is \(2+2+3+3+2+1+1+2+2+2=20\).
Check: the route includes each of the eight original edges \(AB,BC,CD,DE,EF,FA,AC,DF\) at least once, includes precisely the additional copies \(AC'\) and \(DF'\), and ends at \(A\), where it began. Its computed weight \(20\) agrees with the lower bound \(16+4=20\), so it is optimal.
Worked Example: The Other Minimum Pairing Also Works
Again take \(V=\{A,B,C,D,E,F\}\) and edges \(AB(2),BC(2),CD(2),DE(2),EF(2),FA(2),AC(3),DF(1)\). The other minimum pairing is \(\{A,F\},\{C,D\}\). Duplicate \(AF\) and \(CD\), each of weight \(2\), for an extra cost of \(2+2=4\).
One closed route in the augmented graph is \(A-B-C-A-F-D-C-D-E-F-A\). Its traversals are \(AB,BC,AC,AF,DF,CD,CD',DE,EF,FA\). The weight is \(2+2+3+2+1+2+2+2+2+2=20\). Each original edge is covered, the repeated traversals are exactly one extra \(AF\) and one extra \(CD\), and the route returns to \(A\). Its weight again matches \(16+4=20\).
A Common Mistake
Choosing a convenient path instead of a shortest path. For the pairing \(\{A,C\},\{D,F\}\), one could duplicate \(A-B\) and \(B-C\) to connect \(A\) to \(C\), and duplicate \(DF\). That adds \(2+2+1=5\), giving a route weight of \(16+5=21\). It is a valid augmentation, but it is not optimal: the direct edge \(AC\) has weight \(3\), so duplicating \(AC\) and \(DF\) adds only \(3+1=4\). Always compare shortest-path weights before choosing which edges to duplicate.
The pairing calculation is a lower-bound argument as well as a construction method. Any closed route must add enough traversals to correct the parity of every odd vertex. Comparing pairings ensures that this added cost is as small as possible; duplicating the chosen shortest paths then turns that cost into an actual route.
Check Your Understanding
Use the graph with \(V=\{A,B,C,D,E,F\}\), weight-\(2\) edges \(AB,BC,CD,DE,EF,FA\), weight-\(3\) edge \(AC\), and weight-\(1\) edge \(DF\).
- Which four vertices have odd degree, and what is the sum of the original edge weights?
- What is the weight of a shortest path from \(C\) to \(F\)? Give a path attaining it.
- Calculate the pairing costs for all three pairings of the odd vertices.
- If \(AC\) and \(DF\) are duplicated, why does every vertex have even degree?
- For the route \(A-B-C-A-C-D-F-D-E-F-A\), list the duplicated traversals and verify its total weight.