# Selected topics in finite mathematics/Minimum spanning trees

Jump to navigation
Jump to search

A minimum spanning tree for a graph is a subgraph that includes every vertex, is a tree, and has the smallest possible total edge weight.

## Objectives

[edit | edit source]connect all vetices, avoid making a circuit, and create subgraph with the least weight

## Details

[edit | edit source]**Tree**: A subgraph containing some of the vertices and edges, such that there are no cycles in the tree. The tree must also be connected.

**Spanning**: A subgraph spans the original graph if it includes every vertex.

**Minimum Spanning Tree**: a tree within a graph with the smallest possible total edge weights.

To find a minimum spanning tree, begin by putting the edge with the lowest weight in your tree. Make sure it doesn't create a cycle. Repeat this process until you have spanned the entire graph.