A spanning tree of a connected graph G is a connected subgraph of G
having no cycles. Every connected graph has a spanning tree. For
example, the following graph has *four* distinct spanning
trees.

Spanning Trees:

In general a graph will have very many spanning trees. Recall that the

**Example:**
weights added to the graph above

- spanning tree S1 has weight 3+2+4 = 9
- spanning tree S2 has weight 2+4+1 = 7
- spanning tree S3 has weight 3+2+1 = 6
- spanning tree S4 has weight 3+4+1 = 8