1,451 views

In a connected weighted graph with $n$ vertices, all the edges have distinct positive integer weights. Then, the maximum number of minimum weight spanning trees in the graph is

1. $1$
2. $n$
3. equal to number of edges in the graph.
4. equal to maximum weight of an edge of the graph.
5. $n^{n-2}$

### 1 comment

Distinct weights: $1$ (unique)

Cycle graphs: $n$

Complete graphs: $n^{n-2}$

There will be unique min weight spanning tree since all weights are distinct.
Option is A.

### 1 comment

The reason it is 1 because, at each step, for any cut of the graph, we would have unique light edge crossing the cut and hence it would be fairly straight forward to select that edge.No Choices here.

OPTION a is correct

--> if all weights are distinct values then there exist unique min/max spanning tree.(option a)

Knowing the other option is also important while preparation ::

--> if graph is cyclic graph(n vertices) with same edge weights then there exist n spanning trees.(option b/c)

--> //y if graph is complete graph(n vertices) with same edge weights then there exist nn-2 spaning trees (option e).

//up vote if you  agree.

Awesome explanation for option b/c
if graph is cycle graph then there will be n spanning tree not for cyclic graph always