Spanning tree

Recall that a connected graph contains at least one subgraph that is a tree. If the tree connects all the vertices within the graph, it is called a spanning tree.

Properties

• If the graph has $n$ nodes, the spanning tree will have $n-1$ edges.

Types

• Minimum spanning tree

Example

A connected graph on the top, and the spanning tree on the bottom.