This question is motivated by a problem on a local programming competition (you can find the original problem statement here: http://maratona.algartelecom.com.br/files/12maratona.zip , problem E on the pdf, but it's in portuguese).
Basically the problem is: Given an initial complete graph with N vertices and a list of K edges removed from this graph, find the number of possible Hamiltonian cycles.
After much thinking during and after the competition, I could not find a solution to the problem.
The number of Hamiltonian cycles on a complete graph is (N-1)!/2 (at least I was able to arrive to this result myself during the contest haha).
It seems to me that if you take only one edge out, the result would be (N-1)!/2 - (N-2)! Reasoning behind it: suppose a complete graph with vertices 1, 2, 3 and 4, if you take out edge 2-3, you can calculate how many hamiltonian cycles are there using that edge by considering it a vertice, thus you would have "vertices" 1, (2,3) and 4. There are 3! ways of ordering them, but since every "rotation" of a path (ex: 1-(2,3)-4 and (2,3)-4-1) use the same edges, there are 3 rotations possible in this case, thus it becomes 3!/3 Also every "reverse" cycle use the same edges (ex: 1-(2,3)-4 and 4-(2,3)-1), so it becomes 3!/3*2, and since you can arrive the (2,3) both from any side, it would become 3!*2/3*2 = 2! (more generally, (N-2)!). This seems to work, please point out any mistake I've made.
The problem is that, when you remove multiple edges, you are recounting the removal of some paths if you do this for each one (ex: if you remove 2-3 and 4-5, you are counting twice the removal of all the cycles that use both edges). Also, it gets more complicated if you remove 3 or more edges from the same vertex since no path can use all of them.
I could not get any further than this. Please, if you can help, I also ask you to explain me the thought process to arrive at the solution (or any reading that can help me doing this).
Edit: Adding problem constraints The number of vertices in the problem is at most 300 (therefore, maximum 44850 initial edges). The maximum number of edges taken out is 15.