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.

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 pickone.)
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 for finding Hamilton circuits except that here the result is guaranteed to be the minimum!