Let G be a weighted undirected graph and e be an edge with maximum weight in…
2005
Let G be a weighted undirected graph and e be an edge with maximum weight in G. Suppose there is a minimum weight spanning tree in G containing the edge e. Which of the following statements is always TRUE?
- A.
There exists a cutset in G having all edges of maximum weight.
- B.
There exists a cycle in G having all edges of maximum weight
- C.
Edge e cannot be contained in a cycle.
- D.
All edges in G have the same weight
Attempted by 54 students.
Show answer & explanation
Correct answer: A
Key idea: an edge that belongs to a minimum spanning tree is a minimum-weight edge across the cut obtained by removing that edge from the tree.
Remove the edge e from the given minimum spanning tree. This splits the tree into two components and defines a cut that separates those components.
Because the tree is minimum, the weight of e is at most the weight of any other edge crossing that cut; otherwise we could swap in a lighter crossing edge and produce a lighter spanning tree.
Given that e has maximum weight in the entire graph, no crossing edge can be heavier than e, so every edge crossing this cut must have weight equal to the weight of e (the maximum).
Therefore there exists a cut whose crossing edges are all of maximum weight. Hence the statement 'There exists a cutset in G having all edges of maximum weight.' is always true under the given conditions; the other listed statements are not guaranteed.
A video solution is available for this question — log in and enroll to watch it.