So what's a principled way to take a given cut and make it better?

Well, let's just focus on very simple modifications.

Let's suppose the only thing we're allowed to do is take a vertex from one of the two

groups say, from group A, and move it to group b.

For example, in the green network I've showed you on the right-hand

part of this slide, if we envision taking the vertex v and

moving it from A to B, we get a superior cut.

Why is that true?

Well here are the two ramifications of moving v from A to B.

So, first of all, the two edges incident to v that used to be crossing the cut,

they no longer cross the cut.

When we put v over on the right hand side the two edges who's

other end points are in B those edges get sucked in internally to B.

They are no longer crossing the cut.

On the other hand, the good news is, is that the three edges incident to v with

the other endpoint in A they used to be internal to the group A, but when we bring

v over to the right hand side to the group B, now those three edges cross the cut.

So we lost two edges from the cut but we gained three so

that's a net improvement of one more edge crossing the cut.

In general this argument shows that for any vertex so

that the number of edges incident to it that are not crossing the cut,

if that's bigger than the number which are crossing the cut incident to it,

Then switching sides with that vertex will improve the cut.

And the improvement is exactly the difference between the two quantities

d sub v and c sub v.