Let $G=(V,E)$ be a graph, let $s,t$ be vertices of $G,$ and suppose each edge $e$ has a nonnegative weight $c_e.$ We know that an st$-$cut $(U)$ intersects every st$-$path.

$($a$)$ Suppose $S$ is a set of edges that contains at least one edge from every st$-$path. Show that there exists an st$-$cut $(U)$ that is contained in the edges of $S.$

$($b$)$ The weight of an st$-$cut $(U)$ is defined as

$c((U))$:$={\displaystyle \underset{\text{e}\text{i}\text{n}(U)}{\overset{?}{}}}{c}_e$

Find an IP formulation for the problem of finding an $st-$cut of minimum weight, where we have a binary variable for every edge and a constraint for every st$-$path.

$($c$)$ Show that the formulation given in $($b$)$ is correct.