A matching in a graph is a set of edges without common vertices. In other words, it's a set of disjoint edges. And the maximal matching in a graph, is such a matching that if you add any edge to it, it's not longer matching. So a maximal matching is a matching which cannot be extended to a larger one by edge and new registry. And the maximum matching is a matching of the largest size. But in this lesson, we will be only interested in matchings in bipartite graphs. Since in a bipartite graph, all edges go from one part to the other one. A matching is a set of edges from one part to the other one. And we'll often want to find a matching, which covers all the vertices from one part of the bipartite graph. So, it will be a set of edges such that they cover all the vertices in one part, and connect them to different vertices in the other part. Why would we want to do this? For example, we would like to cover all the job openings by the applicants. This would be a matching. Here's an example. This is a good job assignment and also it's a matching. It's a set of disjoint edges. Or I might want to cover all of the students by rooms they like. This would be a matching too. But in this specific case, we know it's impossible. And there is Hall's theorem. Hall's theorem tells us exactly when it is and when it's not possible, to cover all the vertices of one side from bipartite graph by a matching. But in order to understand the statement of Hall's Theorem, we first need to define the neighborhood of a set of vertices. If we have a graph G and we set some set of vertices in it, S. Then the neighborhood of S, which we will denote by N of S, is a set of all vertices connected to at least one vertex in S. All the neighbors of vertices from S. And then Hall's theorem says that in a bipartite graph which has one part L and the other part R, There is a margin which covers, say, all the vertices from the left part, if and only if the following condition holds. For every subset of vertices on the left, the number of their neighbors on the right is greater than the size of the subset. So Hall's theorem says that if for every subset of the vertices on the left, they have more neighbors on the right, than there is a matching which covers all the vertices on the left. And it also says that there is some subset of vertices on the left, which have fewer neighbors on the right, then there is no such good matching. Here's an example. In this graph, we know that there are three people, Carol, And Francis, which only like two rooms. And Hall's theorem says okay, this is exactly this set, S On the left, which has three vertices, C, E and F. And they have fewer neighbors on the right, they have only two neighbors. This is why there is no such a good matching in this graph. There is no matching in this graph which covers all vertices on the left.