TIFR CSE 2013 | Part B | Question: 17

Question

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

• A. $1$
• B. $n$
• C. equal to number of edges in the graph.
• D. equal to maximum weight of an edge of the graph.
• E. $n^{n-2}$

Comments

Distinct weights: $1$ (unique)

Cycle graphs: $n$

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

Answer 1

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

Comments

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.

Answer 2

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 n^n-2 spaning trees (option e).

//up vote if you  agree.

Comments

Awesome explanation for option b/c

---

if graph is cycle graph then there will be n spanning tree not for cyclic graph always