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

The answer should be Option A because edge $e$ is the lightest safe edge connecting $X$ and $Y$ so the minimum spanning tree of $G$ must contain $e$ (Greedy and optimal choice).
While option $(B)$ might seem correct but it is not always true. One such case is when $G$ is not connected therefore there might not be any path between $s$ and $t$.
Since the question is about definitely TRUE, $(B)$ is incorrect and $(A)$ is the only correct option

Lets say $AC =1$, $CD = 2$ ,$BD = 3$ and  $AB=4$

Then if  $s= A$  and  $t= B$ then $AC$  is the lightest edge crossing $X$ and $Y$ where  $X = { A }$  and $Y = { C, B, D}$
But clearly $AC$ is not on the shortest path from $A$ to $B$. The shortest path is $AB = 4$.

Comments

neel19 the minimum edge e has one node in X and one node in Y.

---

nice explaianation

---

If you closely see it is the cut property of MST ,If you partition the graph into two disjoint sets (here X and Y), the minimum weight edge across the cut (here e) must belong to the MST.

Answer 2

The minimum weight edge on any s-t cut is always part of MST. This is called Cut Property. This is the idea used in Prim's algorithm. The minimum weight cut edge is always a minimum spanning tree edge. Why B (the weighted shortest path from s to t) is not an answer? See below example, edge 4 (lightest in highlighted red cut from s to t) is not part of shortest path. 

Comments

Shouldn't minimum weight edge 'e' be directly connected to s and t? As mentioned in the question that 'e' is minimum among those edges that have one vertex in X and another vertex in Y. Please feel free to correct me if I am wrong.

---

Nice Point

Answer 3

Answer for 82 b) is option a) A path from s to t in MST.

T is the spanning tree and E_T is the edge set of the tree.

Let L denote the set of all paths P_e in T where e is any edge in E_G. For g ∈ E_T , we define the congestion of g as the number of paths in L in which g is an element:

c(g, T) = |{P_e ∈ L : g ∈ P_e}|. 

We then define the congestion of G embedded onto T as the maximum c(g, T) over all edges g in E_T :

c(G : T) = max{c(g, T) : g ∈ E_T }. 

The tree congestion of G, denoted t(G), is the minimum value of c(G : T) over all trees T in T_G. Similarly, the spanning tree congestion of G, denoted s(G), is the minimum value of c(G : T) over all spanning trees S in S_G:

t(G) = min{c(G : T) : T ∈ T_G},

s(G) = min{c(G : S) : S ∈ S_G}

Please refer to the link 

http://www.math.csusb.edu/reu/dt07.pdf

Comments

could someone explain this in an easier way?

---

I think answer to B part is option B.

(A)----5---(B)----5---(C)
 |                     |
 |----------7----------|

So in this example, A-C Shortest path is 7. But that will not be the path included in minimum spanning tree. Because spanning tree would be A->B->C

---

Yes you are true but acc. to question congestion (ato c ) is max  weight among  edges lies from a to c. Therefore for a to c in MST  congestion=5.

From a to c in weighted shortest path congestion = 7.

But you may be true in some cases when direct path is less than MST

Answer 4

 

Option: (A) the minimum weighted spanning tree of G

Consider the following graph-

Here, (A, D) is the edge e with weight 1.

The shortest path S to T is (S, T) which does not contain e. Therefore, option (B) is false.

Also, we can see that e is not part of every path from S to T. Therefore, option (C) is false.

Similarly, we show that there can be certain graphs where e is part of the shortest path from S to T.

However, we can see that e is the edge with the minimum weight that connects the vertex set X to vertex set Y, therefore, it must always be present in the MST.

Therefore, the correct option is (A).

Comments

@Debargha Bhattacharj

AD is nothing but another name of ST according to question. Isnot it??

Actually among option A) and B) both could be true.

But A) is more meaningful and logical than B).

So, A) is best choice. rt??

---

@srestha

AD is nothing but another name of ST according to question. Isnot it??

I don't think so. Actually, s and t are two specific vertices in the vertex sets X and Y respectively, which, in the figure, I have mistakenly represented using equivalent uppercase letters.

Now, it is mentioned in the question that among all the edges that connect some vertex in X to some other vertex in Y, e is the edge having the minimum weight. In the above example, e is actually the edge AD with weight 1. 

Now, using the example of the above graph, we can eliminate option (B), (C) and (D).

---

yes, right.

Answer 5

For 82b answer is clearly option B and this concept is used in Link State Routing Algorithm.

Comments

the answer is A not B , the shortest path doesnt guarantee minimum congestion path.

---

I think answer to B part is option B.

(A)----5---(B)----5---(C)
 |                     |
 |----------7----------|

So in this example, A-C Shortest path is 7. But that will not be the path included in minimum spanning tree. Because spanning tree would be A->B->C

---

Can anybody explain what is congestion here??

Answer 6

A) Since it is the minimum weighted edge it will automatically be selected in the MST

B) We suppose that from s to t there is a vertex involved s-->a-->t now s-->a is the edge with the max weight, and s-->t by other path has a comparatively cheaper path, so the least weighted edge might now always be included

C) Explanation to B solves this also

D) This is also not always possible as there can be paths with comparatively expensive weights which do not include this path