On common edges in optimal solutions to traveling salesman and other optimization problems (Q1105496)

Relationships between the symmetric traveling salesman problem (TSP), the minimum perfect matching problem (MPM) and the minimum spanning tree problem (MST), defined on a complete graph with n vertices where a cost is given for each edge, are explored. The main result shows that: if n is even, there exist optimal solutions to TSP and MPM which have at least two common edges; there exist optimal solutions to TSP and MST which have at least two common edges; and if n is even, there exist optimal solutions to MPM and MST which have at least one common edge. Problem instances are presented to demonstrate that these lower bounds on the number of common edges can be attained, thus proving that no stronger result is possible.