What is a Spanning Tree?

A spanning tree of a graph is a subgraph that connects all nodes using exactly $n-1$ edges, where $n$ is the number of nodes. No cycles allowed. If you have $5$ nodes, the spanning tree has exactly $4$ edges. Add one more edge and you create a cycle.

Remove an edge and the graph becomes disconnected. Think of it as the skeleton of the graph: minimum edges, maximum connectivity. The question becomes: which $n-1$ edges give you the lowest total weight?