> Construct a graph G’ = (X’, E’) whose vertex set consists of all odd-degree vertices in G and whose edge set contains an edge joining each pair of vertices. Let the weight of each edge equal a very large number minus the length of a shortest path between the corresponding two vertices in graph G as found by the Floyd algorithm.
> Next, the postman should find a maximum-weight matching for graph G’ using the maximum-weight matching algorithm.