Minimum spanning trees via linear programming

Here's a linear program that solves the minimum spanning tree problem.

Minimize c'x

subject to
x(γ(S)) ≤ |S| - 1 for all nonempty proper subsets of vertices
x(E) = |V| - 1
x ≥ 0

For a vector b (indexed by the edges of the graph) and a set of edges A, b(A) denotes the sum of the components of b indexed by edges in A. For a set of vertices, S, γ(S) denotes the set of edges with both endpoints in S. c is the vector of edge costs.

A theorem of Edmonds shows that the optimal solution to this program is an indicator vector for a minimum spanning tree.

Taken from Cook, Cunningham, Pulleyblank, and Schrijver