Bissoy.com
Doctors Medicines MCQs Q&A

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 

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  Correct Answer II only

I. If e is the lightest edge of some cycle in G, then every MST of G includes e          (INCORRECT)

Let G = (V, E) is a graph with 4 vertices and 5 edges. 

Here, cycle contains the edge weights (3, 4, 5) but edge weight 3 is not included in the MST.

So, if is the lightest edge of some cycle in G, then every MST of G may or may not include e.

II. If e is the heaviest edge of some cycle in G, then every MST of G excludes e          (CORRECT)

According to the cycle property of MST, same example as above. If there is heaviest edge in cycle, then we will exclude it from the MST because there are other low-cost edges are available to include in MST (because edge weights are distinct here).

Related Questions

There are seven persons - A, B, C, D, E, F and G. They have different weights. The weight of second heaviest person is 185 kg and the weight of second lightest person is 85 kg. Sum of weight of C and D is 290 kg. Only Three persons have more weight than D. E is heavier than both F and G but F is not lightest. The weight of A is 250 kg. Sum of weight of F and G is 135 kg. B is heavier than both C and D but C is not lightest. The weight of D is 140 kg. The weight of E is obtained from removing weight of C from weight of A. Who is the Fourth lightest person? 
There are seven persons - A, B, C, D, E, F and G. They have different weights. The weight of second heaviest person is 185 kg and the weight of second lightest person is 85 kg. Sum of weight of C and D is 290 kg. Only Three persons have more weight than D. E is heavier than both F and G but F is not lightest. The weight of A is 250 kg. Sum of weight of F and G is 135 kg. B is heavier than both C and D but C is not lightest. The weight of D is 140 kg. The weight of E is obtained from removing weight of C from weight of A. Who is the fifth heaviest person? 
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?
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?
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 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
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 an undirected connected graph with distinct edge weight. Let emax be the edge maximum weight and emin the edge with minimum weight. Which of the following statements are false?
What is the condition for a tree to be weight balanced. where a is factor and n is a node? >= a*weight and weight >= a*weight. b) weight >= a*weight and weight >= a*weight. c) weight >= a*weight and weight >= a*weight. d) weight is a non zero
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?