Minimal Spanning Tree

Definition

Minimal Spanning Tree

Let $G=(V,E)$ be a finite undirected connected graph with edge-weight function $w:E\to \mathbb{R}$. A minimal spanning tree of $G$ is a spanning tree $T=(V,F)$ whose total weight

$$w(T):=\sum _{e\in F}w(e)$$

is smallest among all spanning trees of $G$:

$$T\in \underset{S\text{ spanning tree of }G}{\mathrm{argmin}}w(S).$$

The word minimal refers to this total weight, not to inclusion of the edge set. Equal edge weights can give $G$ several minimal spanning trees.