Question

Analytical Solution :

Definition

A Minimum Spanning Tree (MST) of a connected, undirected, weighted graph is a subgraph that:

1. Connects all vertices
   
   

2. Contains no cycles
   
   

3. Has (n − 1) edges where n is the number of vertices
   
   

4. Has the minimum possible total edge weight

5. The code constructs a complete graph K₅ using the NetworkX library.

6. In a complete graph, every pair of distinct vertices is connected by an edge.

7. The minimum spanning tree of this graph is computed using NetworkX’s built-in function.

8. Since all edges in K₅ have equal weight, any spanning tree with four edges is valid.

9. The resulting spanning tree connects all five vertices without forming cycles.

10. The edges of the spanning tree are printed to show its structure explicitly.

11. A spring layout is used to assign positions to the vertices for visualization.

12. The original complete graph is drawn in light colors for reference.

13. The spanning tree edges are highlighted in red to distinguish them from other edges.

14. The final plot visually demonstrates how a spanning tree is extracted from K₅.

Python Code

Output: