Spanning Tree

Definition

Spanning Tree

Let be a finite undirected connected graph. A spanning tree of is a tree

Thus keeps every vertex of , but selects only enough edges to connect them without a cycle. Consequently, .