This link provides a guide for bounding solutions to the traveling salesman problem (TSP). In it, the author gives a lower bound on the optimal cost of any tour. For each vertex $v$ in the problem:
$$\text{cost of any tour} >= \frac{1}{2}\sum_{v\in V}\text{(sum of each $v$'s two least cost edges)}$$
(by the way, I'm not sure if there's better notation; this seemed least confusing to me and is the same as the guide uses)
My question: How is this proved? I think that the idea here is that we're adding each node's least cost in and out edges (we need to both get to and leave each city). If those happen to be a neighbor's in or out edge, we divide by two to avoid double counting.
This intuition (why we divide by two) makes sense if the problem has three vertexes (since there are only three possible edges), but I'm not convinced this is a valid bound for larger graphs. Can someone please provide some intuition or a sketch of how this might be proved?
Best Answer
The proof/stems from the following $3$ observations about a tour $T$
Keeping (1) - (3) in mind, what is the total weight $W$ of $T$? If we denote by $w(e)$ the weight of an edge $e$ we might consider $$ \sum_{v \text{ in } T}[w(t_1(v)) + w(t_2(v))], $$ where $t_1(v)$ and $t_2(v)$ are the two distinct edges in $T$ adjacent to $v$. But since every edge in $T$ is adjacent to two vertices $v$, this sum contains the wait of each edge $e$ in $T$ twice, and hence equals $2W$. Since (3) is summarized by the statement $w(t_1(v)) + w(t_2(v)) \geq w_1(v) + w_2(v)$, we conclude
$$ W = \frac{1}{2}\sum_{v \text{ in } T}[w(t_1(v)) + w(t_2(v))] \geq \frac{1}{2}\sum_{v \text{ in } T}[w_1(v) + w_2(v)], $$ which is the desired lower bound.