the 6 edges you can add to the cycle 1-2-3-4-5-6-7-1

to make this the only cycle are 1-3, 1-4, 1-5, 1-6, 3-5, 3-6.

You can add 3-7 to this and
still have a solution for my problem,

which gives a 7-edges-removed answer.

the 9 edges you can add to the cycle 1-2-3-4-5-6-7-8-1

to make this unique are 1-3, 1-4, 1-5, 1-6, 1-7, 3-5, 3-6, 3-7, 5-7

Similarly, 3-8 can be added
to this without affecting 1 to 8 paths,

as well as 5-8, for 9 removed edges.

Scott

hmmn, you're right.

i wonder whether you can only get one more edge in general

by specifiying a particular edge in the cycle. the same

thing seems to hold for the n=6 and n=5, for the same reasons.

No, the K8 above adds both
3-8 and 5-8. Looking at the general

way you have constructed these, I'd say you can add ceiling((n-4)/2),
always

by connecting 3, 5, ... , n-3 to n. Assuming that the general
construction

always produces a Kn with only 1 Hamiltonean path, I think I can prove
it.

Informally:

Premise: Our Hamiltonean path contains the edge 1-n.

Since 2 is connected to only
1 and 3, the string n-1-2-3 must be

contained in our path. The edge 3-n is now harmless if added
in, as no

Hamiltonean path containing n-1-2-3 can also contain 3-n (unless n=4).

4 is connected to 3, 5 and
1. 1 is full, so 1-4 can't be in our path.

3-4-5 must then be, so n-1-2-3-4-5 must be a string. 5-n is now
harmless

as above.

The reasoning continues thus.

Note that this means 5-7
can be added to K7 as well, so only 6

edges need to be removed. Oops.

Generalizing: Assuming
that one can add

{3-5, 3-6, ... , 3-(n-1), 5-7, 5-8, ... , 5-(n-1), ...} to the outside
edges of a

Kn without producing any additional Hamiltonean paths, the set

{3-5, 3-6, ... , 3-n, 5-7, 5-8, ... , 5-n, ...} is a solution to my
question.

Scott