# Miller-Tucker-Zemlin subtour elimination constraints to obtain a minimum spanning tree I need Miller-Tucker-Zemlin subtour elimination formulation for symmetric traveling salesman problem (STSP) to use to construct a minimum spanning tree. Ie, I need Miller-Tucker-Zemlin formulation for an undirected graph.

Replace each undirected edge $$(i,j)\in E$$ with two directed arcs $$(i,j),(j,i)\in A$$ with the same cost $$c_{i,j} = c_{j,i}$$. For each $$(i,j)\in A$$, let binary variable $$x_{i,j}$$ indicate whether that arc appears in the tree. Let node $$1$$ (arbitrarily) be the root, and omit all arcs into the root. For each node $$i\in N$$, let $$u_i\in [0,n-1]$$ be the MTZ variable. The problem is to minimize $$\sum_{(i,j) \in A} c_{i,j} x_{i,j}$$ subject to \begin{align} \sum_j x_{1,j} &\ge 1 \tag1\\ \sum_i x_{i,j} &= 1 &&\text{for j\in N \setminus \{1\}} \tag2\\ u_i + 1 - u_j &\le n(1-x_{i,j}) &&\text{for (i,j)\in A with j \not= 1} \tag3 \end{align} Constraint $$(1)$$ forces at least one arc to leave the root node. Constraint $$(2)$$ forces exactly one arc to enter each non-root node. Constraint $$(3)$$ eliminates subtours by enforcing the logical implication $$x_{i,j} = 1 \implies u_i + 1 \le u_j$$.
For your sample data, an optimal solution is $$x_{1,6}=x_{3,2}=x_{5,3}=x_{5,4}=x_{6,5}=x_{6,7}=x_{7,10}=x_{8,9}=x_{10,8}=1,$$ $$u_{1}=0, u_{2}=9, u_{3}=8, u_{4}=9, u_{5}=7, u_{6}=1, u_{7}=6, u_{8}=8, u_{9}=9, u_{10}=7,$$ with all other $$x_{i,j}=0$$, yielding objective value $$38$$. (The optimal $$x$$ solution turns out to be unique, but there are multiple possibilities for optimal $$u$$.)