True or False: Flow network with $n$ internal nodes has $2^n$ different cuts with all min capacity

Question

Prove whether true or false: For every $n >0$, there exists a flow network with $n$ internal nodes such that there are $2^n$ different cuts that all have minimum capacity.

I have no idea how to do this. Please help!

Answer 1

Yes, there is indeed such a network. So the answer to your true/false question is True.

Hint: Consider a network $\cal{N}$ with a source $s$, sink $t$, and in addition, internal nodes $v_1,\ldots, v_n$ (so $n+2$ nodes total), where the arcs in $\cal{N}$ are $\{(s,v_i)$; $i=1,\ldots, n\}$ $+$ $\{(v_i,t)$; $i=1,\ldots, n\}$, and all arcs in $\cal{N}$ have capacity 1.

LEFT FOR YOU TO CHECK: That there are indeed $2^n$ different min-capacity cuts.