When does the nearest neighbor heuristic fail for the Traveling Salesperson?
Consider a ladder

a----b----c
|    |    |
d----e----f


Say length of a-b is $2$ and length of a-d is $1$. The optimal route is a-b-c-f-e-d-a, $10$ units long. Starting at a, NN would produce a-d-e-b-c-f-a which is $7 + \sqrt{17} &gt; 11$ units long.

There is actually a four node example, a rhombus

  A
 /|\
B-+-C
 \|/
  D


Say length of B-C is $10$, length of A-D is $24$ and thus length of A-B is $13$. The optimal route is A-B-D-C-A, $52$ units long. NN would produce the path A-B-C-D-A, $60$ units long.