Source
Adapted from my own handwritten and hand-typed notes from Year 1 to Year 3 of my EEE degree
Spanning Tree
A spanning tree of a graph is a subgraph of that is a tree and includes all vertices of . It may leave out some edges of . With vertices it always has exactly edges.
Key facts:
- has a spanning tree if and only if is connected
- a graph can have many different spanning trees
- "spanning tree" only makes sense together with a given graph

Minimum Spanning Tree
A minimum spanning tree (MST) of a weighted graph is a spanning tree with the minimum possible total edge weight. In the example below, one spanning tree has total weight while the MST has total weight .

Application
Each vertex is a city and each edge weight is the cost of laying a fibre optic link between two cities. The MST is the cheapest set of links that still connects every pair of cities, possibly through other cities.
MST versus Shortest Path Tree
These two trees are often confused:
- an MST minimises the total weight of all edges in the tree, and has no start vertex
- a shortest path tree minimises the path length from one start vertex to every other vertex, see Dijkstra's Algorithm
An MST is built greedily with Kruskal's algorithm.