+For any $i$, $1 \le i \le \mathsf{N}$, let $zi_{\mathsf{N}}$ (resp. $ti_{\mathsf{N}}$ and $bi_{\mathsf{N}}$)
+be the occurence number of element $i$ in the sequence $u_0, \dots, u_{l-2}$
+(resp. in the sequences $s_{i_1}, \dots , s_{i_l}$ and $v$)
+in step (\ref{item:nondet}) of the algorithm.
+
+Due to the definition of $u'$ in step~(\ref{item:u'}),
+$3.zi_{\mathsf{N}} + ti_{\mathsf{N}}$ is the
+ number of element $i$ in the sequence $U$.
+It is clear that the number of element $i$ in the sequence $V$ is
+$2bi_{\mathsf{N}}$ due to step (\ref{item:VW}).
+We thus have the following system:
+$$
+\left\{
+\begin{array}{lcl}
+3.zi_{\mathsf{N}} + ti_{\mathsf{N}} + 2.bi_{\mathsf{N}} + \textit{TC}_{\mathsf{N}-2}(i) &= &\textit{TC}_{\mathsf{N}}(i) \\
+zi_{\mathsf{N}} + ti_{\mathsf{N}} + bi_{\mathsf{N}} & =& \textit{TC}_{\mathsf{N}-2}(i)
+\end{array}
+\right.
+\qquad
+\Leftrightarrow
+$$
+
+\begin{equation}
+\left\{
+\begin{array}{lcl}
+zi_{\mathsf{N}} &= &
+\dfrac{\textit{TC}_{\mathsf{N}}(i) - 2.\textit{TC}_{\mathsf{N}-2}(i) - bi_{\mathsf{N}}}{2}\\
+ti_{\mathsf{N}} &= & \textit{TC}_{\mathsf{N}-2}(i)-zi_{\mathsf{N}}-bi_{\mathsf{N}}
+\end{array}
+\right.
+\label{eq:sys:zt1}
+\end{equation}
+
+In this set of 2 equations with 3 unknown variables, let $b_i$ be set with 0.
+In this case, since $\textit{TC}_{\mathsf{N}}$ is even (equal to $a_{\mathsf{N}}$
+or to $a_{\mathsf{N}}+2$), the variable $zi_{\mathsf{N}}$ is thus an integer.
+Let us now prove that the resulting system has always positive integer
+solutions $z_i$, $t_i$, $0 \le z_i, t_i \le \textit{TC}_{\mathsf{N}-2}(i)$
+and s.t. their sum is equal to $\textit{TC}_{\mathsf{N}-2}(i)$.
+This latter consraint is obviously established if the system has a solution.
+We thus have the following system.
+
+
+
+\begin{equation}
+\left\{
+\begin{array}{lcl}
+zi_{\mathsf{N}} &= &
+\dfrac{\textit{TC}_{\mathsf{N}}(i) - 2.\textit{TC}_{\mathsf{N}-2}(i) }{2}\\
+ti_{\mathsf{N}} &= & \textit{TC}_{\mathsf{N}-2}(i)-zi_{\mathsf{N}}
+\end{array}
+\right.
+\label{eq:sys:zt2}
+\end{equation}
+
+The definition of $\textit{TC}_{\mathsf{N}}(i)$ depends on the value of $\mathsf{N}$.
+When $3 \le N \le 7$, values are defined as follows:
+\begin{eqnarray*}
+\textit{TC}_{3} & = & [2,2,4] \\
+\textit{TC}_{5} & = & [6,6,8,6,6] \\
+\textit{TC}_{7} & = & [18,18,20,18,18,18,18] \\
+\\
+\textit{TC}_{4} & = & [4,4,4,4] \\
+\textit{TC}_{6} & = & [10,10,10,10,12,12] \\
+\end{eqnarray*}
+It is not hard to verify that all these instanciations verify the aformentioned contraints.
+
+When $N \ge 8$, $\textit{TC}_{\mathsf{N}}(i)$ is defined as follows:
+\begin{equation}
+\textit{TC}_{\mathsf{N}}(i) = \left\{
+\begin{array}{l}
+a_{\mathsf{N}} \textrm{ if } 1 \le i \le c_{\mathsf{N}} \\
+a_{\mathsf{N}}+2 \textrm{ if } c_{\mathsf{N}} +1 \le i \le c_{\mathsf{N}} + d_{\mathsf{N}}
+\end{array}
+\right.
+\label{eq:TCN:def}
+\end{equation}
+
+
+We thus have
+$$
+\begin{array}{rcl}
+\textit{TC}_{\mathsf{N}}(i) - 2.\textit{TC}_{\mathsf{N}-2}(i)
+&\ge&
+a_{\mathsf{N}} - 2(a_{\mathsf{N}-2}+2) \\
+&\ge&
+\frac{2^{\mathsf{N}}-r_{\mathsf{N}}}{\mathsf{N}}
+-2 \left( \frac{2^{\mathsf{N-2}}-r_{\mathsf{N-2}}}{\mathsf{N-2}}+2\right)\\
+&\ge&
+\frac{2^{\mathsf{N}}-2N}{\mathsf{N}}
+-2 \left( \frac{2^{\mathsf{N-2}}}{\mathsf{N-2}}+2\right)\\
+&\ge&
+\dfrac{(\mathsf{N} -2).2^{\mathsf{N}}-2N.2^{\mathsf{N-2}}-6N(N-2)}{\mathsf{N.(N-2)}}\\
+\end{array}
+$$
+
+A simple variation study of the function $t:\R \rightarrow \R$ such that
+$x \mapsto t(x) = (x -2).2^{x}-2x.2^{x-2}-6x(x-2)$ shows that
+its derivative is strictly postive if $x \ge 6$ and $t(8)=224$.
+The integer $\textit{TC}_{\mathsf{N}}(i) - 2.\textit{TC}_{\mathsf{N}-2}(i)$ is thus positive
+for any $\mathsf{N} \ge 8$ and the proof is established.
+
+
+% \begin{table}[ht]
+% $$
+% \begin{array}{|l|l|l|l|l|l|}
+% \hline
+% \mathsf{N} & 3 & 4 & 5 & 6 & 7\\
+% \hline
+% a_{\mathsf{N}} & 2 & 4 & 6 & 10 & 18\\
+% \hline
+% \end{array}
+% $$
+% \label{tab:an}
+% \caption{First values of $a_{\mathsf{N}}$}
+% \end{table}
+
+For each element $i$, we are then left to choose $zi_{\mathsf{N}}$ positions
+among $\textit{TC}_{\mathsf{N}}(i)$, which leads to
+${\textit{TC}_{\mathsf{N}}(i) \choose zi_{\mathsf{N}} }$ possibilities.
+Notice that all such choices lead to a hamiltonian path.
+
+
+
+
+
+%%% Local Variables:
+%%% mode: latex
+%%% TeX-master: "main"
+%%% ispell-dictionary: "american"
+%%% mode: flyspell
+%%% End:
