Proving that greedy algorithm on TSP does not produce optimal solution I know that solving a TSP requires considering all possible cycles in the graph, and that a nearest neighbor greedy algorithm does not always produce the shortest path. I found this answer that gives a counterexample for such a greedy algorithm, but it only consider starting from a specific vertex (A). My question is, if we apply this greedy algorithm `n` times starting at each of the `n` vertex, why wouldn't it yields an optimal short path? I didn't manged to come up with any counterexample yet.

Here is a counterexample where the optimal solution is of weight $13$ but it takes more than $100$ if we use the greedy algorithm starting from any vertex:

![enter image description here](