## 9.2 Outline

- Trees
- definition
- spanning tree

- Minimum spanning trees
- weight
- weighted graph
- definition
- Kruskal’s algorithm
- 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.