Intuition: We know that for a given network N(G(V,E),s,t,c)
, anf a maximum flow f
, every minimal cut in N
is saturated under f
.
As fir out problem, we can infer that the cut {s},V-{s}
is not necessarily minimal - What if we create a network in which the edges adjacent to s
are much larger than those of a minimal cut?
Try to think of a counter example satisfying this condition.