Here is the answer.

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.


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.

        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.