This looks a lot like the way you determine the chromatic polynomial,
but in a some sense "reversed": you know the values of your most "complicated" graphs
instead of iterating until you have reached the simplest ones.
Consider one edge $e$, then the number of hamiltonian cycles in
$G$ equals the number of cycles in $G-e$ (those that do NOT use the edge)
plus the number of cycles in $G/e$ (those that DO use the edge).
This can be transformed into a recursive algorithm: you know the values for
the complete graphs, and all other intermediate values you require
are the result of removing a smaller list of edges from a smaller complete graph.
However this will not perform at all on anything but the smallest examples
and it certainly will not give you anything like a closed formula for the number
of hamiltonian cycles. I am not at all sure if this is an acceptable solution.
EDITED AFTER REQUEST FOR DETAILS:
Consider next pseudocode.
int function h(int n, List l)
{
if (l is empty) { return number of hamilton cycles in K_n }
create new list lNew;
return h(n, l minus last element) - h(n - 1, lNew);
}
This function $h$ calculates the number of hamiltonian cycles in $K_n$
when the edges of the list $l$ are missing.
You use the recurrence $h(G-e)=h(G)-h(G/e)$, so you repeatedly put
one edge back into the graph until you have put back everything.
You have to decide on how to represent the edges on the list.
One option is to represent each edge on $l$ simply as a pair of numbers in the range $1..n$.
The only tricky part is the creation of the list $lNew$.
You cannot just copy its elements from the list $l$, since
they refer to edges of a $K_{n-1}$ after the recursion, so depending on the edge you are removing
you need to manipulate the list elements.
I have no clue how this will perform with the numbers you mention. The most important thing will be that the list of edges is not too long, since that will determine the depth of the recursion. Be sure to use some kind of 'big integer' arithmetic or find other ways to avoid large numbers.
The question can be interpreted as asking how many ways there are to construct a Hamiltonian cycle under these constraints. Since we know $\{1,2\}$ must be in the cycle, it seems reasonable to assume that we start at vertex $1$ and the first edge traversed is $\{1,2\}$. From here, the rest of the cycle is given by a permutation of the remaining vertices $\{3,4, \dots, n\}$ under the constraint that 3 and 4 have to be consecutive. Similar to your idea of treating $\{3,4\}$ as a single vertex, we can permute these $n-3$ objects ($n$ vertices, minus the two we already used and treating 3 and 4 as a single unit) in $(n-3)!$ ways. Then there are 2 orientations for the $\{3,4\}$ edge, so we multiply to get a total of $2(n-3)!$ Hamiltonian cycles.
In your example, we do indeed get $2(5-3)! = 4$ such Hamiltonian cycles.
As a side note, you can generalize this result. If the $k$ "fixed edges" comprise $p$ vertex-disjoint paths, then the number of Hamiltonian cycles should be $2^{p-1}(n-k-1)!$. There's $p-1$ paths to orient, $n - k - p$ vertices which are still on their own, and $p-1$ paths to place as a single unit somewhere in the permutation (so we permute $n-k-1$ objects in this step).
Best Answer
Let $G=(V,E)$ be a simple directed graph with at least two vertices such that each pair of distinct vertices are connected by a directed edge (in one direction only), and such that no nonempty proper subset of $V$ is a sink.
Let $n=|V|$.
We want to show that $G$ has a cycle of length $n$.
Let $p_1,...,p_k\in V$ be such that $p_1...p_k$ is a path of maximum length.
Since $\{p_k\}$ is not a sink, it follows $k > 2$ and, for some vertex $v$, there is an edge from $p_k$ to $v$.
By maximality of $k$, it follows that $v\in \{p_1,...,p_{k-2}\}$, hence $G$ has a cycle.
Let $a_1...a_ma_1$ be a cycle of maximum length.
Necessarily, $m\ge 3$.
If $m=n$, we're done, so assume $m < n$.
Our goal is to derive a contradiction.
Let $A=\{a_1,...,a_m\}$.
Let $B=\{b\in V{\setminus}A{\,\large{\mid}\,}ab\;\text{is an edge for some}\;a\in A\}$.
Since $A$ is not a sink, $B \ne {\large{\varnothing}}$.
Let $b\in B$.
By maximality of $m$, if $a_i\in A$ is such that $a_ib$ is an edge, then $a_{i+1}b$ is also an edge (where $a_{m+1}$ is interpreted as $a_1$), else we can enlarge the cycle $a_1...a_ma_1$ by replacing $a_ia_{i+1}$ with $a_iba_{i+1}$.
It follows that $ab$ is an edge for all $a\in A$.
Let $C=V{\setminus}(A\cup B)$.
Since $B$ is not a sink, it follows that $C\ne {\large{\varnothing}}$, and moreover, $bc$ is an edge for some $b\in B$ and some $c\in C$.
Since $c\not\in A\cup B$, it follows that $ca$ is an edge for all $a\in A$.
In particular, $ca_2$ is an edge.
But then we have edges $a_1b,bc,ca_2$, hence $a_1bca_2...a_ma_1$ is a cycle of length $m+2$, contrary to the maximality of $m$.