retagged by
1,797 views
15 votes
15 votes

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}$
retagged by

2 Answers

Best answer
18 votes
18 votes

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

edited by
14 votes
14 votes

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.

Answer:

Related questions