Next we'll look at a proof that the Ford-Fulkerson algorithm is valid, known as the max-flow min-cut theorem. It also proves that the two problems are equivalent. We need a couple more definitions to, to show, first we want to show the relationship between a flow and a cut. So in this case we've got a cut where T is on one side and all the other vertices are on the same side as S. And what we talk about is the flow across the cut. And that, what that is, is the sum of the flow on it's edges that go from S to T, minus the amount that goes the other way. That's the flow across the cut. So this, what's called the flow value lemma is that, if you have a flow then for any cut. The net flow across the cut is the value of the flow. That's called the flow value lemma. Doesn't matter what the cut is, this, this is a max flow, a flow with value 25 and every cut is going to have 25 flowing across it. So, this cut, this is a more complicated cut where S and these three vertices are colored. So the flow of a, across that cut has to take the all the edges that go from a gray vertex to a white one. So, there's ten plus ten, plus from a gray vertex to a white one, five plus ten + 00. Then, we have to subtract off the edges that go from a white to a gray one. So we add up all the ones that go from gray to white. Ten + ten + five + ten + zero + zero and subtract off the two that go from a white to a gray and, still, the net value across the flow is the same, the value of the flow. That's the flow value lemma that gives a particular relationship between flows and cuts. And that's not too difficult to prove by induction on the size of one of the sets. For example, if we do an induction on the size of the set containing T, it's certainly true when that set consists of just T, because the value of the flow is exactly equal to the edges coming into T. And then to prove by induction, you can move any vertex from A to B in local elibriums, local equilibrium's going to make sure that the flow value limma is true. And so that's, that's how it's proved. And a corollary of that is that, that outflow from S is equal to the inflow to T, which is equal to the val, all equal to the value of the flow. And that's also easy to see in all of our examples. So to get started let's, let's look at what's called weak duality. If, F is any flow at all, in network. If AB is any cut. The value of the flow is going to be less than or equal to the capacity of the cut. So in this case value of flow is 27 and the capacity of the cut is 30. Value of the flow is always less than or equal to the capacity of the cut. And well the net flow across a cut has got to be less than less than or equal to it's capacity 'coz it's at least that and then if there's any edges going the other way, they get subtracted to compute the lugnut flow. So a weak duality, is that, that's an easy thing to prove. So what we want to prove are these two theorems. The max-flow min-cut theorem is really two theorems combined called the augmenting path theorem that says the flow's at max-flow if and only if there's no augmenting paths, and that the value of the max-flow equals the capacity of the min-cut. In any network. And the way we prove that is to prove that the following three conditions are equivalent. Again this is a proof that's a little intricate logically. It's worthwhile for me to go through it, but to really understand it you're going to need to read it carefully and convince yourself that these three conditions work. So here's the three conditions that we're going to prove our equipment. First one is, there is a cut, there's some cut whose capacity equals the value of the flow. The second one is that f is a max flow. So if there's a cut whose capacity equals the flow then f is a max flow. And if f is a max flow there's such a cut. And then the third one is that there's no augmenting path. So we're going to prove those three conditions are equivalent. And we'll do it with a little logic trickery. So first we could prove that one implies two. If there exist a cut capacities equals the value flow, then f is the max flow. Alright, so suppose that we have such a cut, capacity is equal the value of the flow then any other flow by weak duality, flow is going to be less than or equal to the capacity of that cut, . In fact that cuts equal to the value of the flow, so therefore, that's the maximum, max flow. The value of any flow, if less or equal in value of f, so it's the max flow. So that proves that one implies two. Okay. Now we're going to prove two implies three. One implies two, and also two implies three. That also means one implies three. So in order to prove that we're going to prove the counter-positive. So we'll prove that not three implies not two. That is, if there is an augmenting path then F is not a max flow. Well, that's pretty straightforward, then, 'cuz that's what we do in the algorithm. We could improve the flow by sending flow along the path. So it can't be a max flow. So that's, pretty easy. If that was a max flow, there's no augmenting path cuz if there is an augmenting path, that's not a max flow. So that's the, second, part of the proof. And now the third part of the proof, will prove that three implies one. So, that'll give you, the circular logic condition that proves that they're all equivalent. So we want to prove that if there is no augmenting path, then there is a cut in this capacity that equals the value of the flow. So if there's no augmenting path. Then what we're going to have is a cut where A is the set of vertices. That are, connected to S by an undirected path with no full forward or empty backward edges. And so there has to be such a cut if there's no odd many path. S has got to be in A and T has got to be in B otherwise there will be a path from A to B with no four, four front and empty backward with edges and the capacity of that cut equals the net flow across the cut but all the four edges are fallen, all the backward edges are empty so that's exactly equal to the value of the flow. So if there's no augmenting path then we can demonstrate a cut whose capacity equals the value of the flow and that is completes the proof of the max flow and the cut theorem. Sorry. Alright. So the one last step is if we have computed a max-flow, then what we can do is compute the min-cut by computing the set of vertices. And we can do that just by a graph search. We start at S and if there's a path that has no, has a, a forward edge that's not full then we follow that path and if we have a backward edge that's not empty, we follow the path. And we just do a, a graph search to get to all the vertices that we can reach with forward edges that aren't full, and backward edges that aren't empty. And then we treat the full forward edges and the back empty edges as not being there. Otherwise, we do just a regular graph search. And that's, going to give us, the, the, then the set of edges that define by that cut are going to be the min-cut. So, not difficult to compute a min-cut from a max-flow. So that's a proof of the augmenting path there min, max-flow min-cut there.