Let $G = (V, E)$ be a directed graph with edge capacities $c: E \rightarrow \mathbb{R}_{\geq 0}$, $s,t \in V$. Assume there is an edge $(u, v) \in E$ such that it has full capacity in every max $(s,t)$-flow. Then there exists at least one minimum $(s,t)$-cut $(X, V\backslash X)$ in G such that $u \in X$ and $v \in V \backslash X$.
I have been trying to prove this question for hours, using contraposition and a proof by contradiction. I think I'm missing something. Can you help me out?
Hint: Let $c_0$ be the minimum capacity of an $(s,t)$-cut, and let $c_1$ be the minimum capacity of an $(s,t)$-cut with $u\in X$ and $v\in V\setminus X$. If $c_1>c_0$ then you can decrease the capacity of $(u,v)$ by $\min(c_1-c_0,c(u,v))>0$ without changing the minimum cut.