Now we'll explain some application of this Ford Fulkerson theorem. But here the word application is understood in a mathematical sense, so it's not a real application. We just use one theorem to prove another one, and this theorem is about perfect matching. And again, warning, you should not mix mathematics and real life. So we are using this marriage terminology without any claims about the institute of marriage in the society. So in our simplistic we have n men and n women. And there are some pairs for which both participants agree to marry and one man can agree to marry with several womens, it is okay. But I would want to find a perfect matching when this doesn't happen. A perfect matching is one to one correspondent. It's a set of pair, of end pairs, which include all n men and all n women once. And this is just a bipartite graph, if we will draw it so we have a bipartite graph. And we want to delete some edges, so we get some one to one correspondence between these [INAUDIBLE]. And here the picture, I'm sorry to using so bad names for men and women. So we have men a, b, c, d, e and women p, q, r, s, t. And, I just, here are some examples of what pairs are okay for both participants. So is there a perfect matching or not, what do you think? Look at this picture, is there a perfect matching? It's easy to find three pairs, for example, this red line show three pairs. Can you find five pairs or even four pairs not without collisions? Actually, it's not possible, three is the maximum number, and there are some simple argument. And, look, there's green, green dots here, so let's look at men a, c, d, and e. And if you look carefully, you see that there are two women, q and t. And all these men do not agree to any other. So there are four men and only two women. So two of these four men will remain unused. So the maximal matching without collisions is only three persons out of five, so no perfect matching. And this Hall's theorem says that this is only obstacle to perfect matches. So let's give a mathematical statement, imagine we have a bipartite grapgh with n vertices on the left and n vertices on the right. And when it doesn't have a perfect match, this graph doesn't have a perfect matching, if, and only if, there's an obstacle. And the obstacle is, there exists some k at some k vertices, okay, sorry, k vertices on the left. And there is no, they don't have enough right neighbors, so if we look a these k vertices on left and we look at all the neighbors, the neighbors of any of them, and there are less than k neighbors. Then of course, you cannot find pairs for all those k people. It just was the same obstacle that we had with four and two. If such an obstacle exists, there is no perfect matching. And it's obviously it's an obstacle, but what is not obvious, that this is the only kind of possible obstacles. If there is no obstacle of this type, then the perfect matching exists. This is what the Hall theorem says. So this is the statement, and then we need to prove it. And the proof is the reduction to and let's look at this reduction. We have the same graph in the middle. And now these edges are edges of high capacity in one direction. It's difficult to draw arrows in a reasonable way. So just, all these edges go left to right and have high capacity. What really restricts the flow is here. The source is connected to all the left vertices, but with edges of capacity 1. So this integer flows, it's only 0 or 1. And the same for B, there are n, so there are n vertices here. So the n integers which go from B to the destination, each has capacity 1. So it can carry 1 or 0, and we'll look for flows in this network. And they are very closely related to matchings. This is what pipes are for left to right and large capacity in the middle. And, if we have a matching, here is the claim. The matching is actually an integer flow of size n, why? So, if we have a matching, then, of course, we can easily organize a flow, everything goes, all pipes are used. Then in every vertex, we have some matching pair, so we just send to the pair. Then everything is collected and sent to me, very easy, if there is a match. Another thing is what is easy to understand if matching has a flow of size n means they're matching regularly. So if we have a flow of size n, this means that all the edges are full. And if the flow is integer, matching is an integer flow of size n. If the flow is integer, then of course, this should go somewhere. In one direction you can split it into different spots. So you should go in one direction and, of course, you shouldn't come to the same vertex. Because if two 1s come here, then they will stuck here and the oil will be lost here. So we have only pipe of capacity 1, so matching is an integer flow of size n, exactly. And so, we apply Ford and Fulkerson and conclude that if there is no matching, there is no flow of size n. And if there is no flow of size n, then is a cut of size less than n. And we will see that the cut is an obstacle of the type we are looking for. What is the cut in general? So cut is a set of vertices, which contain A and doesn't contain B. And it may contain some vertices in the left part and in the right part. For our Ford and Fulkerson, there is nothing special in bipartite graph, just somewhere. So I use the same letter C, but of course there's the Cs for the source. And there are left C and right C vertices. Now we can think what is in the cut. So cut is just made of the parts, and what are the outgoing edges. So I try to show them, so they can go out here. And there are all edges which go outside the left, C this is cut edges of edges. And if there is some vertex which go from left C to the vertex outside the right C. Then it's also a cut vertex, and the last chance to go outside C is to start here in C and then go to B. So there are outgoing edges of three types. But if we look at the minimal cut, then the second type is impossible. Because these edges have large capacities. So if one of them is included in the cut then the capacity of the cut is very large, so it cannot be minimal. So in the minimal cut there is no edges of this type. And what does it mean, no edges of this type? So no edge going from left C to something outside the right C. This means that this right C contains all the neighbors of left C. All the neighbors of vertices here are inside the sights. And it just should remind you of the obstacle thing. Let's try to make some computation, imagine we have K. K here, and then we have n- K edges which are in the cut. And there is no edges here, and the cut is smaller than n. Each edge is capacity 1, so, if cut is smaller than n then these edges are smaller than K, because n- K here. So, to get some less than n we should have something here smaller than K. And look, so we have here K vertices. We have less than K vertices, and we know that these edges do not exist. That all edges going from this C go in this C. So it's exactly an obstacle which we wanted to find in Hall's theorem. So Hall's theorem is a corollary of [INAUDIBLE]. This is just summarizing, if we have a cut less than n then this left C is bigger than right C. And this is the other requirement for the obstacle in Hall's theorem