# Upper and lower bound for travelling salesman path.

Let $G$ be a complete graph with weights. $MST(G)$ is the length of it's minimal spanning tree and $TSP(G)$ is the length of minimal travelling salesman path (length I suppose it's the sum of weights on the path/tree). The minimal travelling salesman is not the standard one, because the salesman can visit cities multiple times (though he has to end up in the same one), therefore it's not a hamilton cycle, and can be though of as a path on the spanning tree. I have to prove, that the following inequalities hold.

$$MST(G) \leq TSP(G) \leq 2MST(G)$$

I think that I know how to prove $MST(G) \leq TSP(G)$. If we take a minimal travelling salesman path then it's obviously a connected graph, and therefore we can create a spanning tree out of it (if it's not already one). This tree has to have the sum of weights $\geq$ then $MST(G)$, then the original graph also fullfils this inequality.

But what about $TSP(G) \leq 2MST(G)$? I would try constructing the travelling salesman path from the $MST$ to prove it. Let's take that $MST$ from the designated city. Let's DFS it from this city. A DFS path contructed this way designates our traveling salesman route (everytime we enter a child we count the edge, everytime we backtrack in our algorithm we count it again), each edge is counted twice, so our travelling salesman path is of length $2MST(G)$.

Is this correct in any way?

• I believe you have found the standard argument for the upper bound on the travelling salesman path. – Gerry Myerson Jan 13 '14 at 19:02
• So both arguments are correct? Or am I missing some detail? – Arek Krawczyk Jan 13 '14 at 19:03
• There's always room for more detail --- the appropriate amount depends on the circumstances --- but I'd accept both arguments. – Gerry Myerson Jan 13 '14 at 22:29