Jim Boyce

I do hope that Robert Reid claimed the complete solution to the general
problem.  I will follow in his footsteps.

Layout the names of the other edges in an array as follows:

1-3    2-4    3-5    4-6    5-7
1-4    2-5    3-6    4-7
1-5    2-6    3-7
1-6    2-7
1-7

The first row has the edges that skip one path element.
The second row has the edges that skip 2 path elements, and so on.
Each row is sorted by smaller vertex.

If we start with the graph that is just the path 1-2-3-4-... -n, and add
two adjacent edges from the same row to the graph, then we have another
hamiltonian path.  Let the edges be a-b and (a+1)-(b+1).  The path is
1-2-...-a-b -(b-1) -...-(a+1)-(b+1)-(b+2)-...-n.  It consists of the
edges a-b, (a+1)-(b+1), and the path-segments 1-a, (a+1)-b, and
(b+1)-n.  The (a+1)-b path-segment is run backwards.
One of 1-a and (b+1)-n may be null.

This gives equal upper and lower bounds for the number of edges you have
to remove from Kn to leave just the desired hamiltonian path from 1 to
n.  Starting from the left in each row, divide the row into pairs.
(There may be one left over.)  You must remove one edge from each pair,
else there is another hamiltonian path.  That is the lower bound.

Remove the edges in the even-numbered columns.  This leaves a graph with
the desired path.  Furthermore, furthermore, no even-numbered vertex is
connected to another larger-numbered vertex (outside of the desired
path).
So vertex 2 is connected to just 1 and 3.  So the hamiltonian path
starts 1-2-3-...
Vertex 4 is connected to 3 and 5 and smaller numbered vertices that are
already used.  So the path continues ...-3-4-5-...
Vertex 2n is connected to (2n-1) and (2n+1) and smaller numbered
vertices that are already used, so the path continues
...-(2n-1)-2n-(2n+1)-...
So there is just the one hamiltonian path.