TIFR CSE 2021 | Part B | Question: 12

Question

Let $G$ be an undirected graph. For any two vertices $u, v$ in $G$, let $\textrm{cut} (u, v)$ be the minimum number of edges that should be deleted from $G$ so that there is no path between $u$ and $v$ in the resulting graph. Let $a, b, c, d$ be $4$ vertices in $G$. Which of the following statements is impossible?

• A. $\textrm{cut} (a,b) = 3$, $\textrm{cut} (a,c) = 2$ and $\textrm{cut} (a,d) = 1$
• B. $\textrm{cut} (a,b) = 3$, $\textrm{cut} (b,c) = 1$ and $\textrm{cut} (b,d) = 1$
• C. $\textrm{cut} (a,b) = 3$, $\textrm{cut} (a,c) = 2$ and $\textrm{cut} (b,c) = 2$
• D. $\textrm{cut} (a,c) = 2$, $\textrm{cut} (b,c) = 2$ and $\textrm{cut} (c,d) = 2$
• E. $\textrm{cut} (b,d) = 2$, $\textrm{cut} (b,c) = 2$ and $\textrm{cut} (c,d) = 1$

Answer 1

$\textbf{Option E is not possible.}$

$\text{following configuration is not possible, }$

$\text{Here, egde weight denotes the number of path, }$

$\text{If there are 2 paths from between b & c,  and 2 paths between b & d, } \\ \text{then there will be at-least 2 paths between c and d (two paths via b).}$