Graph is undirected!

Dark Mode

509 views

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