Here's a linear program that solves the minimum spanning tree problem.
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