Consider the following undirected graph G

Q. Consider the following undirected graph G:

Choose a value for x that will maximize the number of minimum weight spanning trees (MWSTs) of G. The number of MWSTs of G for this value of x is

Ans: 4

Sol:

To maximize the number of minimum weight spanning trees of G, the value of x will be 5 because it will have two more choices for corner vertex which will maximize maximum number of MSTs.

Now, according to kruskal algorithm for MST:

1. Edges with weights 1 and 3 will be selected first,
2. Now bottom edge with weight 4 will not be selected as will cause cycle on MST,
3. both corner vertices have two-two choices to select the vertices, so these corner edges with weights 4 and 5 will resultant 2*2 = 4 MSTs.

Therefore, total number of MSTs are 2*2 = 4, which is answer.

Note that the value of x is 5, but the number of MWSTs is 4 as shown above.