The route inspection problem

Route inspection and TSP

To travel every edge and return, you must repeat edges between odd vertices. Pair the odd vertices to minimise the extra distance; route length $=$ total weight $+$ that extra. For visiting every vertex (TSP), bound the answer: nearest neighbour gives an upper bound; deleted vertex (MST of the rest $+$ two cheapest edges) gives a lower bound.