Travelling Salesman exercise : discrepancy between solutions I am solving an exercise from Mathematics High Level for the IB Diploma (the Discrete Math book). One of the exercises in graph theory is the following:



*We want to solve the traveling salesman problem for the graph $K$ shown here.

(a) Use the nearest neighbour algorithm starting at vertex $B$ to find an upper bound for the traveling salesman problem.
(b) By removing vertex $B$ find a lower bound.
(c) Write down an inequality  satisfied  by $L$, the length of the shortest Hamiltonian cycle in $K$.


The mark scheme follows:


*(a) $114$
(b) $89$
(c) $89 \leq L\leq 114$
What I got as an answer was very different from the book's answers. For question a, I got $16 + 19 + 17 + 19 + 18 + 22 = 111$. In exercise b, shouldn't the authors specify after deleting such vertex what other vertex to start? And assuming that I would start with vertex A, I would get as a lower bound $73 + 16 + 17 = 106$ (corresponding to the minimum spanning tree plus the two smallest weights connecting B to the tree).
Can someone verify my answers or tell me whether I'm thinking this wrong? Any help is highly appreciated.
 A: Your answer is definitely correct for part (a), with the tour that travels $$B \to A \to F \to C \to D \to E \to B.$$
I can't be fully certain the textbook doesn't have something else in mind for part (b), just because "by removing vertex $B$ find a lower bound" is so vague, but your answer is a correct answer, ad it's definitely better than the textbook's. The scheme you're proposing is to remove vertex $B$, find a minimum-cost spanning tree of the remaining graph, and add on the two lowest-cost edges from $B$. I agree that:

*

*This is a valid way to find a lower bound for the traveling salesman problem. (For any closed tour through all six cities, if we delete the two edges in and out of $B$, the remainder is a path through the other five cities, which is a kind of spanning tree - so its cost is at least that of the minimum-cost spanning tree. Meanwhile, the two edges we deleted cost at least as much as the two cheapest edges from $B$.)


*The minimum cost of a spanning tree is $17 + 18 + 19 + 19 = 73$ (there are two possible spanning trees with this cost, depending on if we use edge $CD$ or $EF$) so this gives us a lower bound of $106$.
The value $89$ given by the textbook is what we'd get if we added the single edge of cost $16$ to the spanning tree, which would be a lower bound on the cost of an open tour beginning at $B$. Technically that's also a lower bound on the cost of a closed tour, but that's silly: you're leaving money on the ground by ignoring the cost of the second edge out of $B$.
(And if we wanted a general lower bound on open tours, $89$ wouldn't do: there is a spanning tree of cost $87$ in the whole graph, and in fact there is an open tour $A\to B \to C \to F \to E \to D$ of cost $87$.)
So, short answer: you're definitely doing reasonable things, and the textbook answer is definitely doing something weird (though we can't be sure what).
