Miller–Tucker–Zemlin formulation of asymmetric TSP

Question

The Wikipedia article https://en.wikipedia.org/wiki/Travelling_salesman_problem#Integer_linear_programming_formulations states two conditions including inequalities about some Uis. I understand how any solution satisfies these two conditions. However, I don't realize Why any assignment that satisfies these two conditions consists of edges that form a Hamiltonian cycle, not a disjoint union of 2-regular graphs. (That's actually the reason we set these two conditions.) Can anybody help?

Answer 1

The article gives a proof by contradiction. If you sum the constraints along a $k$-cycle $C$ that does not contain the depot (city 1), you obtain $$\sum_{(i,j)\in C}(u_i-u_j+n x_{i,j}) \le \sum_{(i,j)\in C} (n-1) \tag1$$ The $u_i$ variables cancel in pairs, and $\sum_{(i,j)\in C} x_{i,j} = k$, yielding $$nk \le k (n-1),$$ which is a contradiction.