# Tag Info

Just adding to the answer of D.W.. Following is a simple example of a graph network that contains an exponential number of $(s,t)$ min cuts. Let the vertex set be $V = \{s\} \cup \{u_{1},\dotsc,u_{n}\} \cup \{v_1,\dotsc,v_n\} \cup \{t\}$. Let the edges set contains the directed edges $(s,u_{i})$, $(u_{i},v_{i})$, and $(v_{i},t)$ for each $i \in \{1,\dotsc,n\}... 2 Build a grid graph, with one node per entry in the matrix, and edges between each pair of adjacent nodes. Also add a source node$s$with an edge from$s$to each blue node, and a sink node$t$with an edge from each white node to$t$. Set the capacity of each edge to 1, except the$s$-to-blue edges have capacity$\infty$, and the white-to-$t$edges have ... 1 Case 1, increase the weight. Consider a path on at least three vertices with capacity 1 for every edge. Max-flow is 1, min-cut is 1. Increase one of the edges' weight, and the max-flow will still be 1, hence the claim is false. Case 2, let$C$be a minimum cut with cost$w(C)$. Decrease the weight of one of the edges in$C$to get a new minimum cost$w'(...