MattF's counterexample, understood properly, is actually a counterexample. His original path sequence in my notation was 142341243 (there are 4 vertices 1,2,3,4 outside the path (octopus heads) and the number shows the leg of which octopus the path vertex is. The key property of this sequence is that if you go from the beginning to the end and make at least one jump, you have to miss at least one vertex. Now surround each vertex $*$ on this path with its own block of the type $aa\dots aa*A$ where each $a$ is connected to $A$ by its own extra vertex (so the jumps between $a$ and $A$ are possible but the jumps between $a$ and $a$ are not and there are no "A" or $a$-connections between the blocks). If we execute at least one long $*$ to $*$ jump between blocks, we will gain at most 4 vertices on the long jumps and at most 2 vertices within each used block with the total gain of $2\cdot 8+4=20$ but we will lose an entire block, so if we have $19$ $a$'s,
the loss outweighs the gain. Otherwise, we have to honestly traverse each block and this does not create any gain either.

It is funny that I have thought of this block construction long ago but missed that $aa\dots aa*A$ possibility. The examples where you have only octopuses all resulted in paths to $*$ from both ends of the block with gains comparable to the total block length, so increasing block length did not help.

I hope that I haven't made a mistake here, but by all means check the details and ask questions if something looks wrong :-)

Edit: Here is a picture of the graph with $19=5$. The path is the horizontal straight line.

[![enter image description here][1]][1]

If you just keep the bottom colored part, this would be exactly Matt F.'s original construction.


  [1]: https://i.sstatic.net/QmsDa.png