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