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 &amp;\sum_{e \in E} c_ex_e \\
\text{s.t. } &amp;\sum_{e \in E_\pi} x_e \geq r(\pi) - 1 \quad \forall \pi \in \Pi, \\
&amp; x \geq 0. \\
\end{align*}
$$
The constraint expresses the following fact:


  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}$.