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.