recategorized by
794 views
3 votes
3 votes

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
recategorized by

1 Answer

0 votes
0 votes
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.
Answer:

Related questions