GATE CSE 2005 | Question: 82a

Question

Let $s$ and $t$ be two vertices in a undirected graph $G=(V,E)$ having distinct positive edge weights. Let $[X,Y]$ be a partition of $V$ such that $s \in X$ and $t \in Y$. Consider the edge $e$ having the minimum  weight amongst all those edges that have one vertex in $X$ and one vertex in $Y$.

The edge $e$ must definitely belong to:

• A. the minimum weighted spanning tree of $G$

• B. the weighted shortest path from $s$ to $t$

• C. each path from $s$ to $t$

• D. the weighted longest path from $s$ to $t$

Comments

If a Graph have a Unique MST then the edges of that Spanning tree is lightest weighted edge on some Cut , not every cut.

---

 

We have an undirected graph $G = (V, E)$ with distinct positive edge weights.

• Partition: The vertex set $V$ is partitioned into two disjoint sets $X$ and $Y$, where $s \in X$ and $t \in Y$.

• The Edge $e$: This is the edge with the minimum weight among all edges that cross the cut (i.e., edges with one endpoint in $X$ and the other in $Y$).

Explanation of each option with reasoning and counter examples 

Option A: The minimum weighted spanning tree of  G (TRUE)

This is a direct application of the Cut Property of MSTs.

The Concept:

For any cut $[X, Y]$ of a graph, if an edge $e$ is the unique minimum weight edge crossing that cut, then $e$ must belong to every MST of the graph. Since the edge weights here are distinct, there is only one unique MST.

Proof:

Suppose $e = (u, v)$ with $u \in X$ and $v \in Y$ is the minimum weight edge crossing the cut, but $e$ is not in the MST $T$.

1. Since $T$ is a MIn spanning tree, there must be a unique path in $T$ connecting $u$ and $v$.

2. Because $u \in X$ and $v \in Y$, this path must cross the cut $[X, Y]$ at least once at some other edge $e' = (u', v')$.

3. We are given that $e$ is the minimum weight edge of the cut, so $w(e) < w(e')$.

4. If we remove $e'$ from $T$ and add $e$, we create a new spanning tree $T'$.

5. The total weight of $T'$ is $W(T') = W(T) - w(e') + w(e)$.

6. Since $w(e) < w(e')$, it follows that $W(T') < W(T)$.

7. This contradicts the assumption that $T$ was a Minimum Spanning Tree. Therefore, $e$ must be in the MST.

Option B: The weighted shortest path from S to t  (FALSE)

While the shortest path from $s$ to $t$ must cross the cut $[X, Y]$, it does not necessarily have to use the minimum edge of that cut. It cares about the global path sum, not the weight of a single edge crossing a specific boundary.

Counterexample:

Consider vertices $\{s, a, b, t\}$ where $X = \{s, a\}$ and $Y = \{b, t\}$.

• Edges crossing the cut: $e = (a, b)$ with weight 1 and $e' = (s, t)$ with weight 5.

• Internal edges: $(s, a)$ with weight 10 and $(b, t)$ with weight 10.

• The minimum cut edge is $e = (a, b)$ with weight 1.

• Shortest Path from $s$ to $t$: The direct edge $(s, t)$ has a weight of 5. The path $s \to a \to b \to t$ has a weight of $10 + 1 + 10 = 21$.

• The shortest path (weight 5) does not contain $e$.

Option C: Each path from S to t (FALSE)

By definition of a cut $[X, Y]$ separating $s$ and $t$, every path from $s$ to $t$ must cross the cut at least once. However, a path can cross the cut using any edge in the cut set, not just the minimum one.

Reasoning:

In the counterexample used for Option B, the path $P = (s, t)$ is a valid path from $s$ to $t$. It uses the edge $e'$, effectively "skipping" the minimum edge $e = (a, b)$. Therefore, $e$ is not in each path.

Option D: The weighted longest path from  S to t (FALSE)

Similar to the shortest path, the longest path is focused on the maximum total sum. It is actually less likely to use the minimum weight edge of a cut because its goal is to maximize the weight.

Counterexample:

Using the same graph as Option B, but change the weight of the direct edge $(s, t)$ to 100.

• The longest path would be the single edge $(s, t)$ with weight 100.

• The edge $e = (a, b)$ with weight 1 is ignored.

---

good explaination

 

Answer 1

Correct answer : A

Explanation:-

Option A: e is the minimum weight edge among all the edges connecting X and Y, so there may be some other edge having weight less than e but belonging to X or Y. However, some edge connecting X and Y has to be included in the MST (otherwise the MST will become disconnected) and this edge will be e because it is the minimum among all the edges connecting X and Y.

Option B: There are two ways to view this option -

i) The path(s) between s and t containing e may not be the shortest path(s) between s and t

ii) The shortest path between s and t may not necessarily contain e.

This is because a path s->x->y->t connecting s and t, (where x->y is an edge connecting the partitions X and Y, s->x is a path from s to x and similarly y->t is a path from y to t) is not depending solely upon x->y. It is also depending upon s->x and y->t. Now even if we minimize x->y by choosing e, there is no guarantee that the other two paths are also minimized. So the minimum path will not necessarily contain e

Option C: e is not the only edge containing X and Y and hence a path from s to t can contain another edge.

Option D: Again, there can be paths from s to t which do not contain e but are more expensive.

Answer 2

So answer is Option A.

Answer 3

Since every edge has distinct edge weights. So, the edge with minimum weight will definitely be present in MST.

Answer 4

Every light edge which crosses the cut will defenitely be present in the minimum spanning tree.(Refer Cormen exercise 23.1-6)….Therefore we can parition in such a way that there is cut present and e crosses it.also s on one side and t on other side.….

(Light edge means the edge with least weight that crosses the cut…)

For Option B,Cand D :

 

Answer 5

Answer: A. the minimum weighted spanning tree of G

Reason:
The edge eee is defined as the minimum-weight edge across the cut [X,Y][X, Y][X,Y], where s∈Xs \in Xs∈X and t∈Yt \in Yt∈Y.
By the Cut Property of MSTs

For any cut in a graph, the minimum-weight edge crossing that cut must belong to the Minimum Spannig Tree (MST).

Since edge weights are distinct, the minimum edge across any cut definitely belongs to the MST.

Why the other options are wrong:

• B: Weighted shortest path from sss to ttt
  The shortest path from sss to ttt does not have to use this edge. Shortest paths do not obey the cut property.

• C: Each path from sss to ttt
  Obviously false — there can be many paths between sss and ttt, and most will not include this specific edge.

• D: Weighted longest path from sss to ttt
  Longest path in a weighted graph is not well-defined unless constraints are given; even then this edge is not guaranteed to appear.

✔ Correct answer: A