TIFR CSE 2016 | Part B | Question: 15

Question

Let $G$ be an undirected graph. For a pair $(x, y)$ of distinct vertices of $G$, let $\mathsf{mincut}(x, y)$ be the least number of edges that should be delted from $G$ so that the resulting graph has no $x-y$ path. Let $a, b, c$ be three vertices in $G$ such that $\mathsf{mincut}(a, b) \leq \mathsf{mincut}(b, c) \leq \mathsf{mincut}(c, a)$. Consider the following possibilities:

1. $\mathsf{mincut}(a, b) < \mathsf{mincut}(b, c) < \mathsf{mincut}(c, a)$
2. $\mathsf{mincut}(a, b) = \mathsf{mincut}(b, c) < \mathsf{mincut}(c, a)$
3. $\mathsf{mincut}(a, b) < \mathsf{mincut}(b, c) = \mathsf{mincut}(c, a)$
4. $\mathsf{mincut}(a, b) = \mathsf{mincut}(b, c) = \mathsf{mincut}(c, a)$

Which of the following is TRUE?

• A. All of i, ii iii, iv are possible
• B. i, ii, iii are possible but not iv
• C. i and iv are possible but neither ii nor iii
• D. ii and iv are possible but neither i not iii
• E. iii and iv are possible but neither i nor ii

Answer 1

The answer is d.  Consider a path a->c->b ,  then  mincut(a,b) >= min(mincut(b,c),mincut(a,c)) .  So if considering this condition to be always true , option i and iii violate the conditions.

Comments

Graph is undirected!