[Math] How many “cuts” does a flow network have

Question

Assuming a single source, single sink digraph with |V| vertices, including source s and sink t. How many “cuts” does a flow network have?

Answer 1

This obviously highly depends on the underlying graph.

If the graph is a line graph consisting of nodes $s = v_1, \ldots, v_n = t$ and edges $(v_1, v_2), \ldots, (v_{n-1}, v_n)$ then there are $n-1$ (possible) cuts $(\{v_1\}\{v_2, \ldots, v_n\}), (\{v_1, v_2\}\{v_3, \ldots, v_n\}), \ldots, (\{v_1, \ldots, v_{n-1}\}\{v_n\})$.

If the graph is a complete graph with nodes $s = v_1, \ldots, v_n = t$ then there are $2^{n-2}$ (possible) cuts since you can pick $s$ and any possible subset of $\{v_2, \ldots, v_{n-1}\}$ as one side of a cut and $t$ and the remaining nodes as the other side.

Karger's algorithm can be used to find all possible cuts. This is, however, a randomized algorithm, so you have no guarantee that the computed number of cuts is correct.