Now, we'll prove Hall's theorem. Hall's theorem, again, says that in a bipartite graph, there exists a matching which covers all vertices of the left part, if and only if the following condition holds. For every subset of the vertices on the left, there are more neighbors on the right. Let's prove the first direction of this theorem. Let's say, if there is a matching, then for every set of vertices on the left, there are more neighbors on the right. While at it, assume there is a matching which covers all the vertices on the left. Then for every subset S of the vertices in the left side will just take the matched vertices on the right. There are at least S of them, that's it. Let's see how it works on an example. Say, in this graph we have a matching which covers all vertices in the left side. Here it is, it's highlighted in orange. Now for every subset of vertices on the left, for example, for these two vertices, I'll just give you two matched vertices on the right. So I have at least that many neighbors. If you ask me to give you at least three neighbors for this three vertices, yeah, again, I will just give you three matched vertices on the right. So we proved one direction with this theorem. If there exists a matching which covers all vertices on the left, then each subset has more neighbors on the right. Now we proved the other direction of Hall's theorem. We know that in our graph, every subset of vertices on the left has more neighbors on the right. And we want to find a matching which covers all the vertices on the left. How do we do this? We'll prove it by induction on the size of L, that is, by induction on the number of vertices in the left part. So we assume that we proved it for all smaller graphs, and now we're proving it for this graph. Let's pick some vertex on the left, and we know that it has at least one neighbor on the right. Okay, so maybe we want to say that this is one edge of our matching. And then we remove these two vertices, have a smaller graph. If there exists a matching in this smaller graph which covers all vertices on the left, then we are good. We'll just say, we take this matching and our original edge, and altogether, this is a matching which covers all the vertices on the left side. We're done. But it's also possible that when we take this vertex on the left and some of its neighbors on the right, we remove these two vertices. And there is no matching which covers all the vertices on the left. This is also a possibility. But now we have a smaller graph, and by induction hypothesis, we know that if there is no matching which covers all the vertices on the left, it means there exists some subset of vertices which has fewer neighbors on the right. For example, these two vertices on the left have only one neighbor on the right. This is the only reason why we might not have a good matching on the smaller graph. But we know that in our original graph, any pair of vertices had at least two neighbors on the right. This means that these two vertices on the left were connected to their removed vertex on the right. Okay, let's return it to our graph. And now we know that these two vertices are connected to these two vertices. So we can find a good matching here. We can find the matching which covers these two vertices. Okay, this will be the first part of our final matching. Let's remove these four vertices, and now we want to find a matching on the remaining part of the graph. So we draw again the removed vertex on the left. And we want to find the matching which covers all the remaining vertices on the left, these two. We'll use induction hypothesis again, we have a smaller graph. So we know that if every subset has more neighbors on the right, then there is a matching. This is exactly what we're going to use here. Well say, okay, let's pick some subset on the left. And we know that before removing these two vertices on the left, they had at least altogether, all four of them, had at least four neighbors. But now we remove two vertices on the left and two vertices on the right, which means that the remaining two have to have at least two neighbors on the right. We've got four vertices with four neighbors, remove two here, remove two here. So the remaining two vertices must have at least two neighbors now. And that's it, we can use induction hypothesis. We know that this means that there is a matching which covers all the vertices on the left. This is the second part of our final matching. We have this matching and that matching, altogether, they cover all vertices on the left. We're done. We just saw how this proof works on an example, and now let's give a formal proof. Formally we will prove it by induction on the number of vertices in the left side, and the base case is when our graph has only one vertex on the left. Then, by this Hall's condition, it has at least one neighbor on the right, so there is a matching of size 1. Induction hypothesis says that we prove it for all graphs with the most k vertices on the left. And the induction step is to prove it for all graphs with k+1 vertices on the left. How do we do this? We pick some vertex on the left, and it has some neighbor on the right. We pick them, try to remove that. If there is a matching which covers all the remaining vertices on the left, then we're done. We take this matching and this edge, and we have a good matching for the original graph. But we also saw that it's possible that there is no such good matching from the remaining part of the graph. But then by induction hypothesis, it means that there exists some subset, S1 of the vertices on the left which has fewer neighbors on the right. Now, we return that removed right vertex, and we know that this subset S1 has exactly S1 neighbors on the right. And Hall's condition also holds for all smaller sets here. So by induction hypothesis, there is a matching between this subset S1 and the corresponding subset T1 on the right. We take this matching and remove those vertices from the graph. Now again, by Hall's condition, in induction hypothesis, there is a matching on the remaining part of the graph which covers all the remaining vertices on the left. We combine this to matchings and get a matching which covers all vertices in the left side.