486 views

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?

1. All of i, ii iii, iv are possible
2. i, ii, iii are possible but not iv
3. i and iv are possible but neither ii nor iii
4. ii and iv are possible but neither i not iii
5. iii and iv are possible but neither i nor ii

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.

### 1 comment

Graph is undirected!