# Minimum spanning tree formulation

Can any expert explain the reasoning behind the constraint in the following formulation of the minimum spanning tree?

To formulate the minimum-cost spanning tree (MST) problem as an LP, we associate a variable $$x_e$$ with every edge $$e \in E$$. Each spanning tree $$T$$ corresponds to its incidence vector $$x^T$$, which is defined by $$x^T_e = 1$$ if $$T$$ contains $$e$$ and $$x^T_e = 0$$ otherwise. Let $$\Pi$$ denote the set of all partitions of the vertex set $$V$$, and suppose that $$\pi \in \Pi$$. The rank $$r(\pi)$$ of $$\pi$$ is the number of parts of $$\pi$$. Let $$E_\pi$$ denote the set of edges whose ends lie in different parts of $$\pi$$. Consider the following LP: \begin{align*} \min &\sum_{e \in E} c_ex_e \\ \text{s.t. } &\sum_{e \in E_\pi} x_e \geq r(\pi) - 1 \quad \forall \pi \in \Pi, \\ & x \geq 0. \\ \end{align*}

• As I suggested the last time you asked a similar question, I suggest working through a small example by hand, and see what happens if you include that constraint and what happens if you leave it out.
– D.W.
Jan 16 '20 at 22:19
• I tried but still not clear. Jan 17 '20 at 0:24
• Cool, why don't you share with us a summary of what you've come up with and show some examples that illustrate why this is interesting/unclear?
– D.W.
Jan 17 '20 at 0:50

Let $$T$$ be a spanning tree, and suppose that we partition the vertex set into $$r$$ parts. There are exactly $$r-1$$ edges of $$T$$ which connect different parts.
For example, if $$T$$ is a tree and $$C,\overline{C}$$ is a cut, then exactly one edge of $$T$$ crosses the cut, that is, connects $$C$$ and $$\overline{C}$$.