Kruskal Mst 095Eeb

1. **State the problem:** We need to find the minimum cost spanning tree (MST) of a graph with vertices $\{A,B,C,D,E,F\}$ and edges with weights: $B-E=1$, $A-F=2$, $C-E=4$, $A-E=5$, $C-F=7$, $A-D=8$, $B-F=12$, $B-D=13$, $C-D=15$. We will use Kruskal's algorithm. 2. **Kruskal's algorithm summary:** Sort all edges by increasing weight and add edges to the MST if they do not form a cycle until all vertices are connected. 3. **Sort edges by weight:** $$ B-E=1, A-F=2, C-E=4, A-E=5, C-F=7, A-D=8, B-F=12, B-D=13, C-D=15 $$ 4. **Select edges step-by-step:** - Add $B-E=1$ (lowest weight). - Add $A-F=2$ (next lowest). - Add $C-E=4$ (connects $C$ to $E$ and $B$). - Add $A-E=5$ (connects $A$ and $E$; check for cycle: $A$ connected to $F$, $E$ connected to $B$ and $C$, no cycle yet). 5. **Check next edge $C-F=7$:** Adding $C-F$ would create a cycle because $C$ and $F$ are already connected through $E$ and $A$. 6. **Add $A-D=8$:** Connects $D$ to the tree without cycle. 7. **Stop:** We have $6$ vertices connected with $5$ edges: $B-E$, $A-F$, $C-E$, $A-E$, $A-D$. 8. **Edges included in MST:** $B-E=1$, $A-F=2$, $C-E=4$, $A-E=5$, $A-D=8$. **Final answer:** The edges included in the minimum cost spanning tree are $B-E$, $A-F$, $C-E$, $A-E$, and $A-D$.