To solve this problem using Kruskal's Algorithm, we need to follow these steps:

1. Sort the edges by their weights in ascending order.
2. Add edges to the Minimum Spanning Tree (MST), starting with the smallest weight, but ensuring no cycles are formed.
3. Repeat until all vertices are connected.

Step 1: List and sort the edges by their weights.

From the graph, the edges and their weights are:

• $AB = 3$
• $AC = 5$
• $AD = 14$
• $AE = 11$
• $BC = 13$
• $BD = 15$
• $BE = 7$
• $CD = 13$
• $CE = 2$
• $DE = 10$

Sorted by weight:

• $CE = 2$
• $AB = 3$
• $AC = 5$
• $BE = 7$
• $DE = 10$
• $AE = 11$
• $BC = 13$
• $CD = 13$
• $AD = 14$
• $BD = 15$

Step 2: Apply Kruskal's Algorithm

• Start with the smallest edge: $CE = 2$ (add to MST).
• Next smallest: $AB = 3$ (add to MST, no cycle).
• Next: $AC = 5$ (add to MST, no cycle).
• Next: $BE = 7$ (add to MST, no cycle).
• Next: $DE = 10$ (add to MST, no cycle).

At this point, all vertices $A, B, C, D, E$ are connected. So, the edges in the Minimum Spanning Tree (MST) are:

• $CE = 2$
• $AB = 3$
• $AC = 5$
• $BE = 7$
• $DE = 10$

Step 3: Answer the Question

Now, let's check which of the listed edges are part of the MST:

• $AE$: No, it's not in the MST.
• $BD$: No, it's not in the MST.
• $CD$: No, it's not in the MST.
• $BC$: No, it's not in the MST.
• $AD$: No, it's not in the MST.
• $DE$: Yes, it is in the MST.
• $AB$: Yes, it is in the MST.
• $AC$: Yes, it is in the MST.
• $BE$: Yes, it is in the MST.

Thus, the edges that are included in the Minimum Cost Spanning Tree are:

• $DE$
• $AB$
• $AC$
• $BE$

Would you like more details on Kruskal's Algorithm or any other part of the solution?

5 Related Questions:

1. What are the differences between Kruskal's Algorithm and Prim's Algorithm for finding an MST?
2. How does the Disjoint Set data structure help in Kruskal's Algorithm?
3. Can you explain how cycles are avoided in Kruskal's Algorithm?
4. What is the time complexity of Kruskal’s Algorithm?
5. How would the MST change if some edge weights were negative?

Tip:

When implementing Kruskal’s Algorithm, sorting the edges first makes it easier to ensure you're always adding the smallest possible edge while avoiding cycles.