Editing Chinese postman problem (section)

==Undirected solution and ''T''-joins==
The undirected route inspection problem can be solved in [[polynomial time]] by an [[algorithm]] based on the concept of a ''T''-join.
Let ''T'' be a set of vertices in a graph.  An edge set ''J'' is called a ''T'''''-join''' if the collection of vertices that have an odd number of incident edges in ''J'' is exactly the set ''T''. A ''T''-join exists whenever every connected component of the graph contains an even number of vertices in ''T''. The ''T'''''-join problem''' is to find a ''T''-join with the minimum possible number of edges or the minimum possible total weight.
 
For any ''T'', a smallest ''T''-join (when it exists) necessarily consists of <math>\tfrac{1}{2}|T|</math> paths that join the vertices of ''T'' in pairs. The paths will be such that the total length or total weight of all of them is as small as possible. In an optimal solution, no two of these paths will share any edge, but they may have shared vertices. A minimum ''T''-join can be obtained by constructing a [[complete graph]] on the vertices of ''T'', with edges that represent shortest paths in the given input graph, and then finding a [[Matching (graph theory)|minimum weight perfect matching]] in this complete graph. The edges of this matching represent paths in the original graph, whose union forms the desired ''T''-join.
Both constructing the complete graph, and then finding a matching in it, can be done in O(''n''<sup>3</sup>) computational steps.

For the route inspection problem, ''T'' should be chosen as the set of all odd-degree vertices. By the assumptions of the problem, the whole graph is connected (otherwise no tour exists), and by the [[handshaking lemma]] it has an even number of odd vertices, so a ''T''-join always exists. Doubling the edges of a ''T''-join causes the given graph to become an Eulerian multigraph (a connected graph in which every vertex has even degree), from which it follows that it has an [[Euler tour]], a tour that visits each edge of the multigraph exactly once. This tour will be an optimal solution to the route inspection problem.<ref>{{citation|first=E.L.|last=Lawler|title=Combinatorial Optimization: Networks and Matroids|publisher=Holt, Rinehart and Winston|year=1976}}</ref><ref name = "EdmondsJohnson">{{citation|first1=J.|last1=Edmonds|first2=E.L.|last2=Johnson|title=Matching Euler tours and the Chinese postman problem|journal=Mathematical Programming|volume=5|year=1973|pages=88–124|doi=10.1007/bf01580113|s2cid=15249924|url=http://www.eecs.umich.edu/%7Epettie/matching/Edmonds-Johnson-chinese-postman.pdf}}</ref>