MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I am looking for an example that demonstrates the necessity of either subtour-elimination or of connectivity constraints in the LP formulation of the MST

In the internet I only could find the LP formulations, but no motivation for the constraints.

The need for topological constraints seems contradictory to me, because demanding the number of edges to be $n-1$, together with the requirement, that at least one edge be adjacent to each vertex, suffice for a connected graph of $n$ vertices to ensure connectivity and a tree topology. Fractional solutions seem also counter-intuitive.

So, where does the need for topoligical constraints in the LP formulation of the MST problem actually come from, resp. when does it arise?

share|cite|improve this question
up vote 2 down vote accepted

I'm not sure that I understand your question properly but the constraints you propose do not ensure connectivity. As far as I guess, you propose to use the following polytope to describe the spanning trees of a graph $G(V,E): \sum_{e\in E} x_e=|V|-1; \sum_{v\in e\in E} x_e\geq 1$ for all $v\in V$ and $x_e\geq 0, e\in E$. But then, for instance, in $K_5$ a triangle and a disjoint edge constitute a vertex of your polytope.

share|cite|improve this answer
thanks for the clarification – Manfred Weis Jul 22 '13 at 10:59

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.