Combinatorial Optimization (Cook et al.) I: The Characteristic Vector of a Minimum Spanning Tree Is an Optimal Solution of the Spanning-Tree Linear ProgramTextbook
A minimum spanning tree (MST) of a connected graph with edge costs is a cheapest set of edges that connects all nodes and contains no circuit. It is the prototype of a combinatorial optimization problem solved exactly by a greedy rule, and it opens Chapter 2 of Cook, Cunningham, Pulleyblank and Schrijver's Combinatorial Optimization (Wiley, 1998). The…