Graph Min Cut Problem

Question

The idea is to give an Flow Network in which the minimum cut goes through a lot of edges. So adding one unit to each edge will change the min cut. The following figure, as a counter example, shows a ow network, which has a min-cut of value 3 which goes through 3 edges, but after increasing each edge by one unit, the min-cut changes to a cut of value 4 which goes through 1 edge.

i ran into a problem, i think, if we have a graph that each of edge weights is integer and bigger than 1, and increase by 1, the min cut (s,t) in two graph remain same. anyone could give me a counter example for such graph?

Answer 1

Theorem: Increasing by 1 each weight of each edge in a graph increases the min-cut value.

Proof:

We mark by $P_i$ the total weight of the $i$th path, which cutting it from the graph will disconnect $s$ from $t$, and by $n_i$ the total number of edges in it. We obviously know that $P_i, n_i$ are positive integers for all $i$'s.

Let $i=1$ be the path of least weight in $G$. We thus have $P_1\le P_i, \forall i$. We increase the weight of each edge by 1 and define the new graph as $G'$. In $G'$, $P'_i=P_i+n_i$. Thus if increasing the weight wouldn't have increased the min-cut value, we would have $P'_i\le P_1$, so $P_1\ge P_i+n_i$, contradicting the fact that $P_1\le P_i,\forall i$.

---

As to the location of the min-cut, it can remain the same or change. Using your graph I will give an example where all the edges are of weight strictly bigger than one and it changes, and one where it doesn't.

Here adding one to all adges will change the location from the three edges to the single-edge:

While here it will remain at the single-edge: