Questions: 3. (8 points) Find the minimum cost spanning tree on the graph below using Kruskal's Algorithm. List the edges which are included in the minimum cost tree.

Solution Steps

The edges, sorted in ascending order of their weights, are: EF (2), AC (3), CD (4), DE (5), AB (4), AE (6), DF (7), BC (5), BE (7), BD (8).

Start with an empty set of edges for the Minimum Spanning Tree (MST). We will add edges in increasing order of weight, as long as adding the edge does not create a cycle.

1. EF (2): Add EF to the MST.
2. AC (3): Add AC to the MST.
3. CD (4): Add CD to the MST.
4. AB (4): Add AB to the MST.
5. BC (5): Adding BC would create a cycle (ABC), so we skip it.
6. DE (5): Add DE to the MST.

We now have 5 edges in a graph with 6 vertices, so we have a spanning tree and can stop.

Final Answer