Consider the following undirected graph with edge weights as shown. The number of minimum-weight spanning trees of the graph is \(\underline{\hspace{2cm}}\).
Show Hint
When multiple edges have the same minimum weight, more than one minimum spanning tree may exist.
Step 1: Identify the minimum-weight edges.
From the given graph, the smallest edge weight is 0.1.
All edges with this weight must be considered first while constructing
a minimum spanning tree (MST).
Step 2: Use properties of minimum spanning trees.
A minimum spanning tree:
• Connects all vertices of the graph
• Has no cycles
• Has the minimum possible total edge weight
When multiple edges have the same weight, more than one MST may exist.
Step 3: Count all valid MSTs.
By examining all combinations of edges with weight 0.1 that:
• Connect all vertices
• Do not form any cycle
We find that exactly 3 distinct spanning trees achieve the
minimum total weight.
Final Conclusion:
The number of minimum-weight spanning trees in the graph is:
