Computer Sciences > Gate 2024 Set-2 > Graph
The number of distinct minimum-weight spanning trees of the following graph is _________

Correct : 9

Explanation:
Let us perform a thorough, rigorous verification using the properties of Minimum Spanning Trees (MST) and the cycle property to confirm why the total number of distinct options is exactly 9.
1. Classify Edges by Weight:
Weight 1 Edges: (a, b), (a, f), (c, d), (d, e)
Weight 2 Edges: (a, g), (b, g), (c, g), (d, g), (e, g), (f, g)
Weight 3 Edges: (b, c), (f, e)
2. Step 1: Including Weight 1 Edges
• All 4 edges of weight 1—(a, b), (a, f), (c, d), (d, e)—must be part of any MST because they are the absolute smallest available choices and do not create any internal cycles.
• Including these edges forms two disconnected trees (sub-components):
    • Left Component: {b — a — f}
    • Right Component: {c — d — e}
    • Isolated Center Node: {g}
3. Step 2: Connecting Components via Weight 2 Edges
The graph has 7 vertices, so an MST must contain exactly 6 edges. We have already selected 4 edges, meaning we need exactly 2 more edges of weight 2 to fully connect the entire graph.
To connect the three pieces without introducing a cycle, we must pick exactly one cross-edge to connect the Left Component to node g and exactly one cross-edge to connect the Right Component to node g. Let's analyze how many valid ways we can choose this pair:
Connections to the Left Component {b, a, f}:
    Node g has three potential incident edges to this component: (b, g), (a, g), (f, g).
    Selecting any single one of these will safely connect node g to the left block without creating a cycle.
    → Number of valid choices for the left side = 3 choices.
Connections to the Right Component {c, d, e}:
    Node g has three potential incident edges to this component: (c, g), (d, g), (e, g).
    Selecting any single one of these will safely connect node g to the right block without creating a cycle.
    → Number of valid choices for the right side = 3 choices.
4. Calculate Total MST Combinations:
Since the structural edge selection on the left component is completely independent of the choice made on the right component, we apply the fundamental product rule of counting:
    Total Distinct MSTs = (Left Choices) × (Right Choices)
    Total Distinct MSTs = 3 × 3 = 9.
5. Conclusion:
Your calculation is entirely correct. There are exactly 9 distinct Minimum Spanning Trees possible for this graph.

Similar Questions

Let G = (V, G) be a weighted undirected graph and let T be a Minimum Spanning Tree (MST) of G maintained using adjacency lists. Suppose a new weighed edge (u, v...
#280 MCQ
Consider a simple undirected unweighted graph with at least three vertices. If A is the adjacency matrix of the graph, then the number of 3-cycles in the graph...
#314 MCQ
Consider a simple undirected graph of 10 vertices. If the graph is disconnected, then the maximum number of edges it can have is ____________.
#661 Fill in the Blanks

Related Topics

No tags found

Unique Visitor Count

Total Unique Visitors

Loading......