Constructing a minimal spanning tree for a graph of N elements is O(N^3).
If the minimal spanning tree is a cycle, you're extremely lucky and your traveling salesman problem is done.
Otherwise, the collective weight of all the minimal spanning tree's edges will be less than or equal to the collective weight of all the edges of the optimal traveling salesman path.
A path around the minimal spanning tree necessarily visits each node twice, as in pre-order tree traversal, so the cost of walking this path is 2x the weight of the sum of all edges of the minimal spanning tree.
Since the weight of the sum of all the edges of the minimal spanning tree is less than or equal to the weight of all the edges of whatever the optimal traveling salesman problem solution is, the cost of walking the path leading around the minimal spanning tree (2x the sum of all its edges' weights) is less than or equal to 2x the cost of walking the optimal traveling salesman solution.
If the minimal spanning tree is a cycle, you're extremely lucky and your traveling salesman problem is done.
Otherwise, the collective weight of all the minimal spanning tree's edges will be less than or equal to the collective weight of all the edges of the optimal traveling salesman path.
A path around the minimal spanning tree necessarily visits each node twice, as in pre-order tree traversal, so the cost of walking this path is 2x the weight of the sum of all edges of the minimal spanning tree.
Since the weight of the sum of all the edges of the minimal spanning tree is less than or equal to the weight of all the edges of whatever the optimal traveling salesman problem solution is, the cost of walking the path leading around the minimal spanning tree (2x the sum of all its edges' weights) is less than or equal to 2x the cost of walking the optimal traveling salesman solution.
