# Section 9.2: Trees and Minimum Spanning Trees

## 9.2 Outline

1. Trees
1. definition
2. spanning tree
2. Minimum spanning trees
1. weight
2. weighted graph
3. definition
4. Kruskal’s algorithm
5. number-of-vertices-and-edges-in-a-tree theorem

## 9.2 Essential Ideas

A tree is a graph which is connected and has no circuits. A tree that is created from another graph by removing edges, but keeping a path to each vertex is called a spanning tree. If the edges of a graph have weight, then we refer to graph as a weighted graph.

Minimum Spanning Tree

A minimum spanning tree is a spanning tree for which the sum of the numbers associated with the edges is a minimum.

Kruskal’s Algorithm

To construct a minimum spanning tree from a weighted graph:

Step 1: Select any edge with minimum weight.
Step 2: Select the next edge with minimum weight amount those not yet selected.
Step 3: Continue to choose edges of minimum weight from those not yet selected, but make sure you not select any edge that forms a circuit.
Step 4: Repeat this process until the tree connects all the vertices of the original graph.

Number-of-Vertices-and-Edges-in-a-Tree Theorem

If a graph is a tree with n vertices, then the number of edges is n − 1.