Bissoy.com
Doctors Medicines MCQs Q&A

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 ?

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 ? Correct Answer <span style="">The edge with the second smallest weight is always part of any minimum spanning tree of G</span>, <span style="">One or both of the edges with the third smallest and the fourth smallest weights are part of any minimum spanning tree of G</span>, <span style="">Suppose S ⊆ V be such that S ≠ ϕ and S ≠ V. Consider the edge with the minimum weight such that one of its vertices is in S and the other in V \ S . Such an edge will always be part of any minimum spanning tree of G</span>

The correct answer is option 1, option 2, and option 3.

Concept:

Option 1:The edge with the second smallest weight is always part of any minimum spanning tree of G.

True, Consider the following graph,

 [ alt="F1 Savita Engineering 28-3-22 D17" src="//storage.googleapis.com/tb-img/production/22/03/F1_Savita_Engineering__28-3-22_D17.png" style="width: 141px; height: 122px;">

The Second minimum cost edge is always in the minimum spanning tree because the second minimum does not form a cycle in the minimum spanning tree. 

Option 2: One or both of the edges with the third smallest and the fourth smallest weights are part of any minimum spanning tree of G.

True, One or both of the edges with the third smallest and the fourth smallest weights are part of any minimum spanning tree of Graph. One of the third or fourth minimum costs in the minimum spanning tree. If the third cost forms a cycle in the minimum spanning tree then the fourth minimum must be in the minimum spanning tree.

Option 3:Suppose S ⊆ V be such that S ≠ ϕ and S ≠ V. Consider the edge with the minimum weight such that one of its vertices is in S and the other in V \ S . Such an edge will always be part of any minimum spanning tree of G.

True, 

Given a cut (S, V−S) of G, recall that an edge (u,v) ∈ E is said to cross the cut if exactly one of u and v is in S. An edge e = (u,v) is a minimum weight edge crossing the cut (S, V−S) if its weight is the smallest of any edge crossing (S, V − S).  Then e = (u,v) must be included in the minimum spanning trees of G.
Let G = (V, E,w) be a connected undirected weighted graph with distinct edge weights. For any cut (U, V − U) of G, the minimum weight edge that crosses the cut is in the minimum spanning tree MST(G) of G.

Option 4:G can have multiple minimum spanning trees.

False,  G can not have multiple minimum spanning trees when all the edges are distinct.

Hence the correct answer is option 1, option 2, and option 3.

Related Questions

Let G be a connected undirected weighted graph. Consider the following two statements. S1: There exists a minimum weight edge in G which is present in every minimum spanning tree of G. S2: If every edge in G has distinct weight, then G has a unique minimum spanning tree. Which one of the following options is correct?
G = (V, E) is an undirected simple graph in which each edge has a distinct weight, and e is a particular edge of G. Which of the following statements about the minimum spanning trees (MSTs) of G is/are TRUE? I. If e is the lightest edge of some cycle in G, then every MST of G includes e II. If e is the heaviest edge of some cycle in G, then every MST of G excludes e 
Let G be a weighted connected undirected graph with distinct positive edge weights. If every edge weight is increased by the same value, then which of the following statements is/are TRUE? P: Minimum spanning tree of G does not change Q: Shortest path between any pair of vertices does not change
Let G be a weighted graph with edge weights greater than one and G' be the graph constructed by squaring the weights of edges in G. Let T and T' be the minimum spanning trees of G and G', respectively, with total weights t and t'. Which of the following statements is TRUE?
Let G = (V, E) be any connected undirected edge-weighted graph. The weights of the edges in E are positive and distinct. Consider the following statements: I) Minimum Spanning Tree of G is always unique. II) Shortest path between any two vertices of G is always unique. Which of the above statements is/are necessarily true?
Let G be any connected, weighted, undirected graph. I. G has a unique minimum spanning tree, if no two edges of G have the same weight. II. G has a unique minimum spanning tree, if, for every cut of G, there is a unique minimum-weight edge crossing the cut. Which of the above two statements is/are TRUE?
Let G be an undirected connected graph with distinct edge weights . Let emax be the edge with maximum weight and emin be the edge with minimum weight. Which of the following statements is false.
The line graph L(G) of a simple graph G is defined as follows: There is exactly one vertex v(e) in L(G) for each edge e in G. For any two edges e and e' in G, L(G) has an edge between v(e) and v(e'), if and only if e and e' are incident with the same vertex in G. Which of the following statements is/are TRUE? (P) The line graph of a cycle is a cycle. (Q) The line graph of a clique is a clique. (R) The line graph of a planar graph is planar. (S) The line graph of a tree is a tree.
Let G be a simple undirected graph. Let TD be a depth first search tree of G. Let TB be a breadth first search tree of G. Consider the following statements. (I) No edge of G is a cross edge with respect to TD. (A cross edge in G is between two nodes neither of which is an ancestor of the other in TD .) (II) For every edge (u, v) of if u is at depth i and v is at depth j in TB , then |? − ?| = 1. Which of the statements above must necessarily be true?
Consider the undirected graph below: Using Prim's algorithm to construct a minimum spanning tree starting with node a, which one of the following sequences of edges represents a possible order in which the edges would be added to construct the minimum spanning tree?