A Spanning Tree of a Graph that minimizes Edge Weight. “MST”.
- i.e. an Acyclic Connected Graph that minimizes Edge Weight
- e.g. Each house is a Vertex, each Edge is Weighted according to the cost of connecting the given pair of houses, the problem is optimally connect a given Graph of houses into a WAN
- Multiple MSTs may be possible for a single graph.
- Any MST must include the minimum edge connecting the two Subgraphs left by any possible Graph Cut