A minimum spanning tree of a weighted connected graph is a spanning tree whose weight is less than or equal to the weight of every other spanning tree of that graph.

But what does **that** mean? Because that statement might not be terribly clear, let’s break it down:

Informally, a *graph* is a set of points called *vertices* that are joined by lines called *edges*. Formally, a graph is an ordered pair of sets (V, E), where V is a finite set of vertices and E is subset of V x V.

A *weighted graph* has a number associated with each edge of the graph. Each number is a *weight* for that edge. The *weight of a graph* is the sum of all those numbers.

A *walk* is a finite sequence of vertices in which each pair of neighboring vertices has an edge between them.

A graph is *connected* if and only if, for every pair of vertices u and v, there is a walk from u to v.

A *path* is a walk that never visits the same vertex twice.

A *cycle* is a path from some vertex back to itself. An *acyclic graph* has no cycles.

A *tree* is a connected, acyclic graph.

A tree *spans* a connected graph if and only if it contains all of the vertices of that graph. A *spanning tree* of a connected graph is a tree that spans the graph.

Now, let’s use these definitions to unpack our initial statement of what a minimum spanning tree is:

Obviously, a minimum spanning tree is a tree. Therefore, a minimum spanning tree is a graph that is [i] connected and [ii] acyclic. That means that [i] each pair of the graph’s vertices has a walk between them and that [ii] none of the graph’s vertices has a path going back to itself.

As a spanning tree, a minimum spanning tree spans a connected graph. That means that it contains all of the vertices of that graph.

As a* *minimum spanning tree, a minimum spanning tree has a weight. Its weight is the sum of the weights of its edges. (To be clear, it derived its edges from the graph that it spans.)

What makes a minimum spanning tree be a **minimum** spanning tree is that its weight is less than or equal to the weight of every other spanning tree that spans that graph.

Hopefully, that clears up what a minimum spanning tree is. Now for the next question: Why are minimum spanning trees important?

Let’s say there is a set of computers that you want to network together. Because it’s expensive to network computers together, you want to find the least expensive way to connect all of them. In other words, you want to construct a minimum spanning tree!

In general, minimum spanning trees let you connect a set of things that are costly to connect at the least possible expense. You can apply minimum spanning trees to road construction, social networks, circuit design, etc., etc.

Now your question should be: How do I find minimum spanning trees? The two most popular algorithms are Prim’s algorithm and Kruskal’s algorithm. I go over Kruskal’s algorithm in this post.