We can see that there are two negative edges in this graph, so most likely they’ll be part of the minimum spanning tree. We’ll start by adding those edges.

From there, we can add edges from vertices D, E, and F. Vertex D and vertex F both have edges with weights of 1, so we’ll add both of those to the graph.

We have to make sure that each time we add an edge to the minimum spanning tree, no cycles appear. What is a cycle? Imagine that we add the edge E-G next; the E-F-G cycle appears.

We’ll remove that edge since it’s not part of the Minimum Spanning Tree. If we observe the graph, vertices C, D, E, F, and G have been added, but vertices A and B have not. Vertex A can be connected either through edge A-C or edge A-B. Since edge A-C is lower in weight, we’ll add that edge.

Edge B has several options. It can enter the MST via edge A-B, B-C, B-D, or B-F. Since B-D has the smallest weight, it’s added to the tree.

Let’s double check to make sure that our solution is correct. We’ll do this by trying to find other optimum routes to each vertex from another vertex, i.e. vertex A. If we want to go from A to B, we could utilize edge A-B, which has a weight of 5, or a series of edges A-C-E-F-D-B, which has a weight of -10. We can repeat this procedure for other routes to B, as well as for other routes to other vertices. We’ll quickly see that the edges that we chose to include in the MST are the optimal edges. These edges create the optimal route between all vertices. We’ll take a more algorithmic approach in the next few articles in finding the minimum spanning tree.