Let $G$ be any connected, weighted, undirected graph.
Which of the following statements is/are TRUE?
Cut set is the set of edges whose removal disconnect the connected graph..so do you not think that cut is also same as cut set and it is min cut set??
@Arjun @Digvijay Pandey please verify
@Sankha Narayan Bose
e1 and e2 also a cutset, then is this diagram satisfying conditions mentioned in the question ?
I donot think it is telling about cut set. Because, if it is a cut set then can cut more than one edge, which is violation of spanning tree
Actually they are telling to remove minimum edge from a graph, (which they described as cut set)
And after that removal, is it forming a MST? As minimum edge edge is unique , so it forming a unique spanning tree
@srestha They are asking about the original graph not the ones you get after cutting.
1. If edge weights are distinct then there exist unique MST.
2. If for every cut of a graph there is a unique light edge crossing the cut then the graph has a unique minimum spanning tree but converse may not be true.
Proof by contradiction:
Lemma: If an edge $e$ is contained in some minimum spanning tree, then it is a minimum cost edge crossing some cut of the graph.
Assume MST is not unique and there exist two MST's $T_1$ and $T_2$
Suppose $e_1∈T_1$ but $e_1 \notin T_2$, if we remove $e_1$ from $T_1$, then we will have disconnected graph with two set of vertices $V_1$ and $V_2$. According to lemma $e_1$ is a minimum cost edge in the cut between $V_1$ and $V_2$.
Suppose $e_2∈T_2$ but $e_2 \notin T_1$, if we remove $e_2$ from $T_2$, then we will have disconnected graph with two set of vertices $V_1$ and $V_2$. According to lemma $e_2$ is a minimum cost edge in the cut between $V_1$ and $V_2$.
Because the minimum cost edge is unique implies $e_1$ and $e_2$ is the same edge. $e_1 \in T_2$ and $e_2 \in T_1$. We have chosen $e_1$ at random, of all edges in $T_1$, also in $T_2$ and same for $e_2$. As a result, the MST is unique.
So both are TRUE.
Answer is (C).