List of top Algorithms Questions on Minimum spanning trees asked in GATE CS

Consider a complete graph \(K_n\) with \(n\) vertices (\(n>4\)). Note that multiple spanning trees can be constructed over \(K_n\). Each of these spanning trees is represented as a set of edges. The Jaccard coefficient between any two sets is defined as the ratio of the size of the intersection of the two sets to the size of the union of the two sets.

Which one of the following options gives the lowest possible value for the Jaccard coefficient between any two spanning trees of \(K_n\)?
Let \(G(V,E)\) be a simple, undirected graph with unique edge weights.
Which of the following statements about the minimum spanning trees (MST) of \(G\) is/are true?
Consider a simple undirected weighted graph \(G\), all of whose edge weights are distinct. Which of the following statements about the minimum spanning trees of \(G\) is/are TRUE?
Let \(G\) be a connected undirected weighted graph. Consider the following two statements:
\(S_1:\) There exists a minimum weight edge in \(G\) which is present in every minimum spanning tree of \(G\).
\(S_2:\) If every edge in \(G\) has distinct weight, then \(G\) has a unique minimum spanning tree.
Which one of the following options is correct?

Consider the following undirected graph with edge weights as shown. The number of minimum-weight spanning trees of the graph is \(\underline{\hspace{2cm}}\).