Question $3$: Maximum flows and connectedness

$($a$)$ A network is said to be $k-$edge$-$connected if it remains connected after removing $k-1$ edges.

Here, we ask you to focus on a specific pair of nodes $s,t.$ Then, the network is said to be

$k-$edge$-$connected as far as $s-t$ are concerned if $s$ can send flow to $t$ upon removal of $k-1$

edges. Formulate this problem as a maximum flow problem.

$($b$)$ A network is said to be $k-$node$-$connected if it remains connected after removing $k-1$ nodes.

Here, we ask you to focus on a specific pair of nodes $s,t.$ Then, the network is said to be $k-$

node$-$connected as far as $s-t$ are concerned if $s$ can send flow to $t$ upon removal of $k-1$ nodes,

other than the source and the terminal themselves. Formulate this problem as a maximum flow

problem.

$($c$)$ As we saw in class, the minimum cut problem can be used to identify the smallest cut value

that separates a source node $s$ to a terminal $t.$ A graph may have multiple minimum cuts of

the same value. As an example, consider the graph in Figure $1.$ What if we are interested in

the minimum cut $($among all minimum cuts$)$ that also minimizes the number of edges we cut?

Propose an $($efficient$,$ i$.$e$.,$ that runs in polynomial time$)$ algorithm to find that cut.

Figure $1$: An example of a graph with two minimum $s-t$ cuts $($for $s=1,t=5)$ of the same

value $(2).$ Cutting edges $(1,2),(3,4)$ or edge $(4,5)$ result in the same value cut.