# Hamiltonian cycles -- Partition function

Assume a complete undirected graph $G'=(\mathcal{V}',\mathcal{E}')$ and the partirion function:

$$\sum_{\boldsymbol{x}\in \{-1,+1\}^n} \prod_{\left(i,j\right)\in \mathcal{E}'} \left[1+x_{i}x_{j}\theta_{i,j}\right],\quad \theta_{\emptyset}=0$$ I would like to expand the product and then sum to find the expanded form of the partition function and I noticed that the only terms which will not sum up to zero after the summation are those for which $$\prod_{(i,j)\in \epsilon }x_i x_j \theta_{i,j}=\pm \prod_{(i,j)\in \epsilon }\theta_{i,j} \quad \forall x_i x_j \in\{-1,+1\}$$ for all the subsets $\epsilon \subset \mathcal{E}$, otherwise the corresponding product will sum up to zero after the summation. Then I tried to solve the equation above and we have the following: find the relationship between $i,j$ for all the pairs $(i,j)$ such that $$\prod_{(i,j)\in \epsilon }x_i =\pm \prod_{(i,j)\in \epsilon } x_j\quad \forall x_i x_j \in\{-1,+1\}$$. It seems like for each $x_i$ which participates to left handside $m$ times should appear $m$ times to the right as $\pm x_{i}$. My intuition is that the graph which is formed from all the edges of each set $\epsilon \subset \mathcal{E}$ such that the above equation is satisfied is a graph with (disconnected) cycles (two regular). To solve this I think it is sufficient to solve the following:

Let $G=(\mathcal{V},\mathcal{E})$ be an undirected graph with $\mathcal{E}=\{(i_r,j_r)$: for $r\in\{1,2.\ldots,R\}\}$. Assume that the sequence of indicies $i_1,i_2,\ldots,i_R\in\mathcal{V}$ is a permutation of $j_1,j_2,\ldots,j_R\in\mathcal{V}$ and not all the permutations are allowed since : it can not exist an edge of the form $(i,i)$ and $(i,j)\equiv(j,i)$. Is it always true that the Graph $G$ is a Hamiltonian cycle or a collection of (disjointed) hamiltonian cycles?
Since I can not find a counterexample I am trying to prove it as follows: Consider the permutation mapping $M:I \rightarrow J$ then for any $(i_k,j_k)\in \mathcal{E}$ we have $(i_k,j_k)=(i_k,M(i_k))$ and we can write the edges in the following order:$$(i_k,M(i_k)),(M(i_k),M(M(i_k))),(M(M(i_k)),M(M(M(i_k)))),\ldots, (M^{R}(i_k),i_k)$$. Is this sufficient?

• Am I missing something? It seems to me that $M(M(i))=i$ for every $i$, as the graph is supposed to be undirected. Mar 17, 2018 at 22:35
• for example: $i_1\rightarrow j_1 \equiv i_{10}$ , $i_{10} \rightarrow j_{10} \equiv i_3$, $i_3 \rightarrow j_3 \equiv i_5$ and we have $M(i_1)=i_{10}$, $M(M(i_1))=i_3$ notice that the mapping is from i's to j's and you can not have $M(M(i))=i$ since $(i,j)\equiv (j,i)$ Mar 19, 2018 at 0:51
• you can walk the other direction by applying $M^{-1}(j)$ where $M^{-1}:J \rightarrow I$ Mar 19, 2018 at 2:03
• What does "fully connected" mean? (This is not a usual technical term.) Mar 19, 2018 at 7:59
• Sorry, I mean complete thank you for pointing that out. Mar 19, 2018 at 15:59

Note that every $2$-regular finite simple graph is a collection of disjoint cycles so it is sufficient to show that the graph is $2$-regular.
• Actually, you cannot get the conclusion you want unless you demand that $i_k$ equals $j_l$ => $j_k$ is not equal to $i_l$. Otherwise, the chosen pair of permutations spans fewer edges than desired and at least one vertex has degree less than $2$. Mar 19, 2018 at 19:02
• With the additional hypothesis you can prove the statement as follows: For any appropriate choice of two permutations $i$ and $j$, the edge set of graph $G$ has $R$ elements : {$i_1, j_1$}, ... , {$i_R, j_R$}. Observe that for every positive integer $k$ smaller than or equal to $R$ , $i_k$ is different from $j_k$ so none of these pairs is actually a singleton. Now let $l$ be any positive integer smaller than or equal to $R$. How many times does l occur in our collection of pairs ? Mar 19, 2018 at 19:47