Spanning Tree

A spanning tree for a weighted graph $G=(V,E,w)$ is a tree $T=(V,E^{\prime })$ in which each vertex is connected and $E^{\prime }\subseteq E$. It is any sub-graph of $G$ that connects all nodes without any cycles.