Suppose we have a Graph $G$ in which weight of all edges is $> 1$ (positive). If we increase weight of all edges by one, why does the minimum cut $(S, T)$ of $G$ into two graphs remain the same?
the following graph if we add all edges by one not change the min-cut
This is a question arise when I read a graph theory book.
By definition, minimum cut is the partition of vertices in two nonempty sets that minimizes the total weight of edges connecting the two parts. Here is an example of how it can change if the weights are all increased by $1$.
Take complete graph $K_n$ with all edges of weight $a$, and attach a new vertex to it by a single edge of weight $b$. The minimum cut will be across the added edge if $b<a(n-1)$, and it will be within $K_n$ if $b>a(n-1)$.
Observe that it is possible to have $b>a(n-1)$ but $b+1<(a+1)(n-1)$; thus, increasing the weights by $1$ can change the position of minimum cut.
Concrete example: $a=2$, $b=11$, $n=6$. Here $b>5a$ but $(b+1)<5(a+1)$.