Minimum Spanning Tree

A tree that covers all Vertices in a graph with minimal weight for its Edge.

Formal Definition

A Tree $T$ s.t $\forall v\in V$ is an endpoint of atleast one edge in $T$ with minimum weights for edges used with $weight(T)={\sum }_{(u,v)}\in Tweight(u,v)$

Alternate Definition

A subgraph of Graph $G$ that:

• Contains all vertices
• Is Connected
• Has no Cycle

Properties

• MST Cut Property

Algorithms

• Kruskal’s Algorithm
• Prim’s Algorithm