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: $\mathsf{mincut}(a, b) < \mathsf{mincut}(b, c) < \mathsf{mincut}(c, a)$ $\mathsf{mincut}(a, b) = \mathsf{mincut}(b, c) < \mathsf{mincut}(c, a)$ $\mathsf{mincut}(a, b) < \mathsf{mincut}(b, c) = \mathsf{mincut}(c, a)$ $\mathsf{mincut}(a, b) = \mathsf{mincut}(b, c) = \mathsf{mincut}(c, a)$ Which of the following is TRUE? All of i, ii iii, iv are possible i, ii, iii are possible but not iv i and iv are possible but neither ii nor iii ii and iv are possible but neither i not iii iii and iv are possible but neither i nor ii Graph Theory tifr2016 graph-theory graph-connectivity + – go_editor asked Dec 29, 2016 recategorized Nov 23, 2022 by Lakshman Bhaiya go_editor 794 views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
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. Vikram Bhat answered Jan 6, 2016 Vikram Bhat comment Share Follow See 1 comment See all 1 1 comment reply akashsheoran commented Dec 29, 2016 reply Follow Share Graph is undirected! 1 votes 1 votes Please log in or register to add a comment.