Note: if you cannot remember what a spanning tree is, revise notes for 3.1 Trees and Spanning Trees.

**Contents**

### Minimum Spanning Trees

- Most connected graphs will have
**multiple**spanning trees. In a**weighted graph**, one of these spanning trees will have the**lowest weight**(i.e. the sum of each edge’s weight is the least). This is known as a**minimum spanning tree**. - Minimum spanning trees are commonly used for
**optimisation**problems. For example, when transferring products between towns, it is advantageous to know the fastest way of doing so.