Properties of Trees

1. IF a graph is a tree, there is one and only one path joining any two vertices.
   Conversely, if there is one and only one path joining any two vertices of a graph, the graph must be a tree.
2. In a tree, every edge is a bridge.
   Conversely, if every edge of a connected graph is a bridge, then the graph must be a tree.
3. A tree with N vertices must have N-1 edges.
4. A connected graph with N vertices and N-1 edges must be a tree. Every connected graph contains a tree.

Spanning Tree
A tree inside of a connected graph that includes every vertex of the original graph is called a Spanning Tree.

Every connected graph has at least one Spanning Tree.

Minimum Spanning Tree
In a weighted connected graph, a spanning tree with the least total weight is called a Minimum Spanning Tree.

There is an algorithm that will ALWAYS find a Minimum Spanning Tree for any connected weighted graph. This algorithm is called Kruskal’s Algorithm.

Kruskal’s Algorithm

1. Find the cheapest edge in the graph. (If there is more than one, just pick one.)
2. Find the cheapest remaining edge in the graph that does not close a circuit. (If there is more than one, just pick one.)
3. Repeat Step 2 until the chosen edges form a Spanning Tree (that is, they reach all the vertices).

THE RESULTING TREE IS A MINIMUM SPANNING TREE FOR THE GRAPH.

Notice that this is similar to the Cheapest Link Algorithm except that here the result is guaranteed to be the minimum!