PROFESSOR: So let's get set to state Hall's theorem in a way that doesn't mention boys and girls. But let's remember the girl-boy setup to start. So the general setup is a bipartite graph H. And a bipartite graph has two sets of vertices-- the girl vertices and the boy vertices.
Formally, there's a set L of H, called the left vertices of H, and a set R of H, called the right vertices of H. The vertices of H altogether are L of H union R of H. Both of these are non-empty. And they don't overlap.
Then the edges of H have the property that they only go between L of H and R of H. That is the definition of a bipartite graph. Now, we're interested in a matching in a bipartite graph. So let's be precise again of what's a matching without having to mention boys and girls and like.
A match is a total injective function from the left vertices to the right vertices. So that means every L vertex, or girl, has a match m of L that is on the other side. And we need this total injective function, match function m, to follow the edges.
What does follow the edges mean precisely? It simply means that the edge l m of l is a legitimate edge of H. Another way to say that is that the graph of this total injective function is a subset of the edges of H.
So we can state the no-bottleneck condition, Hall's condition, as follows. If the size of S is less than or equal to its image under the edges, for every set of left vertices H, that's called Hall's condition, that the size of S is less than or equal to the image of S for every S, then there is a match. So this is a way of precisely stating Hall's theorem.
No boys and girls mentioned. We'll be comfortable going back to the boy-girl language, because it's more memorable and easier to talk about. But just for the record, we have now formally stated, defined bipartite graphs, matches in bipartite graphs, and Hall's theorem really that there is a match when Hall's condition is satisfied without mentioning boys and girls.
The puzzle is, how do you verify that there are no bottlenecks? It's pretty hard. The bottleneck condition involves checking that every subset S of L of H satisfies this cardinality condition. And there are a lot of subsets of L of H relative to the size of the graph, exponentially many.
So we can ask, how do you verify that there are no bottlenecks? Well, it turns out in logarithms classes, you will learn a fairly efficient matching procedure, runs about quadratically, for finding perfect matches when they exist. But there is one particular special case that ensures no bottlenecks that we'll be making use of several times in the term.
And that special situation is when it turns out that every girl likes at least d boys and every boy likes at most d girls. This is called a degree-constrained graph. If a graph is degree constrained, then there are no bottlenecks. So this condition that each girl likes at least d boys and every boy likes at most d girls could have been rephrased as saying that the minimum degree of the girls is greater than or equal to the maximum degree of the boys. But I think expressing it in terms of d maybe makes it a little clearer.
Let's prove this. I'm going to prove that, if you have a degree-constrained bipartite graph, then it, in fact, satisfies Hall's condition. There are no bottlenecks. So we have that, if every girl likes at least d boys and every boy likes to most d girls, there are no bottlenecks. The proof goes as follows.
Let's look at some arbitrary set S of girls. And suppose that the total number of edges that are incident to S has cardinality e. There are e edges that touch vertices in S. Well, that tells us that since every vertex in S has at least d edges out-- maybe more-- d times the size of S has to be less than or equal to the total number of edges coming out of S.
Likewise, all of the edges that come out of S go, by definition, into E of S. And each vertex in E of S can only absorb d edges, d girls. So that means that the total number of edges absorbed by E of S-- that is, at most d times E of S-- had better be bigger than the number of edges that have to be absorbed e. So we get that d times the size of S is less than or equal to the total number of edges incident to S, which is less than or equal to d times the total number vertices in E of S.
Well, I'll cancel the d's. And we have that the size of S is less than or equal to the size of its image. That's the definition of a bottleneck-- The violation of that would be a bottleneck. This says, there's no bottlenecks. And we have proved the degree-constrained condition is sufficient to verify Hall's condition. And by Hall's theorem, it's sufficient to guarantee that there is a match.
Now, there's a lot of graphs with matches that are not degree-constrained. This is not an if and only if theorem. It's just a sufficient condition that comes up often enough that it's worth mentioning. Degree-constrained implies Hall's condition is satisfied, which implies that there's a perfect match.
So let's turn now to the general case of Hall's theorem. And let's talk about proving Hall's theorem. Hall's theorem says that if there's no bottleneck, then there is a match.
So let's begin by setting up a lemma that will play a crucial role. The strategy for proving it is basically going to be to try to break the problem of finding a match for a large set of vertices into sub problems of finding matches for smaller sets of vertices. And by strong induction, Hall's condition will apply to the subsets and will win. Let's look at that more carefully.
So let's begin by supposing that there are no bottlenecks in some bipartite graph H. Well, in particular, if there's no bottlenecks anywhere, then if you restrict yourself to some set S of girls, no subset of that set S is going to have a bottleneck, obviously, because a bottleneck within S would be a bottleneck within the whole graph. So that part's trivial.
What's not trivial and takes a little bit of arguing is that suppose you have a set of girls with the property that the number of boys that are compatible with that set of girls is exactly the same as the number of girls. So technically, the size of S is equal to the size of E of S. In that case, we can argue that there aren't any bottlenecks within the complement of S and the complement of E of S either.
Well, let's look at a picture to illustrate what's going on. So here we have a bipartite graph. And there's S and its image on the right E of S. And we know that a bottleneck here would imply a bottleneck in the whole graph.
What we want to argue is that a bottleneck in the complement of S would imply a bottleneck in the complement of E of S. So there's the complement of E of S. And there's the complement of S.
Now, notice that some edges that come out of the complement of S may very well go into the E of S. That is, this would be a point that's both in E of S and in E of S complement. But we're not allowed to use that point, because we're trying to find a match only within S bar and E of S bar. And what we're really trying to argue is that a bottleneck here would imply a bottleneck in the whole graph.
So let's see if we can argue this. We want to claim that there's no bottleneck between S bar any E of S bar given that there's no bottleneck anywhere and when S and E of S are the same size. So let's suppose that we had a set T over here that was a subset of S bar. And let's look at its image over here in orange.
So we've got that the image of this set T, when we restrict it just to the part that's in the complement of S-- notice I'm leaving out this point here. I'm not taking the image of T. I'm taking the image of T restricted to the points that are not in the image of S. And what I want to know is, could that cause a bottleneck?
After all, I've left out some points that used to be included in the image of T. And so the image of T might have been bigger than T because of those extra points that I'm leaving out, I have to be sure that that doesn't happen. Could there be a bottleneck that has been created by these points that I've left out? Could there be a bottleneck in E of T intersection, a complement to E of S. Could that orange guy be a bottleneck?
Well, if it was a bottleneck, then I'd have a bottleneck in the whole graph. And that's because S and E of S are the same size, because all I do is, if I had a bottleneck there, I would take this set T along with S and this set orange along with E of S, and that would be a bottleneck. Because now, if you look at the size of T, I've added the same amount to the size of T as I've added to that orange set, because E of S and S are the same size.
So if this orange part was smaller than T, then orange part along with E of S is smaller than T union S. And that defines a bottleneck in the whole graph. So again, if there was a bottleneck in here caused by restricting images to the complement of E of S, it means there was a bottleneck in the whole graph. If there's no bottleneck at all, then indeed, there's no bottleneck in this other part of the complement of S and the complement of E of S.
And this gives me a hook on proving Hall's theorem, because that's basically the way I'm going to split the problem into two separate matching parts. So let's now proceed to prove that if there are no bottlenecks in a graph, then there's a perfect match. And it's going to be by strong induction on the number of girls.
So case one is the case that we just examined, that there's a non-empty subset of girls-- a proper subset, not all the girls-- some subset of girls who-- another way to say it is there's a subset of girls that's not empty and its complement is not empty either. And the size of S is the same as the size of E of S. That is, the number of boys that are compatible with this set of girls is exactly the same size as this set of girls.
Well, if there's going to be a match, there has to be one in that subset. And by the lemmas, if there's no bottlenecks anywhere, there's no bottlenecks when I restrict myself to just S and E of S. And also by the previous Lemma, there's no bottleneck in the complement of S restricted to the vertices in E of S.
So this is a new bipartite graph, where I'm using S for the left vertices and E of S for the right vertices. And here, I'm using the complement of S for the left vertices and the complement of E of S for the right vertices. And the previous lemma says that if there's no bottlenecks overall, there's no bottlenecks in either of these two restricted graphs.
So what I can do now is, by induction, since there's no bottlenecks in S, E of S, I can find a match there. So I can match up all of the girls in S with compatible boys in E of S. And I can match up all of the girls that are not in S, in the complement of S, with boys that I haven't used already. And there will be a perfect match there. And then these two separately will provide a match for the entire set of left vertices-- S union the complement of S will be all of the vertices.
And these two matchings don't overlap. So combining them gives a complete matching. That knocks off this case. That's the nice case, where I can find some subset with the number of boys is exactly equal to the number of girls, which means that that has to work by itself. And I worked that one by itself and what's left over by itself. And that's how I can find an overall match.
The second case is that there isn't any set of girls, which are compatible with exactly the same number of boys. Well, since Hall's condition holds, that means that every set of girls actually has to be compatible with a larger set of boys than the number of girls. That is, for every set S, the size of S is strictly less than the size of E of S for every non-empty and proper subset S.
Well in that case, actually finding a match is easy, because now I've got slack. What I can do is just pick an arbitrary girl-- call her g-- and she's got to be compatible with at least one boy, because there's no bottlenecks. In fact, in this case, she'll actually be compatible with these two boys. But all we need is one boy.
Since there's no bottlenecks, if I pick a girl, she's got to be compatible with some boy. And I'm just going to arbitrarily match her with that boy-- match g with b. Now, the consequence of that is that, if I now remove g and b from the graph, I am left with a graph in which at worst I've shrunk the set E of S by that girl that I've matched with B, which means that E of S, which used to be strictly greater than S has gone down by at most one. It's still greater than or equal to E of S.
So I'm left that in the graph after I've removed this g paired with an arbitrary b that she's compatible with, I'm left with a graph that satisfies Hall's condition that has one fewer girl vertex. And so it has no bottlenecks. And therefore, it has a match.
And that match in the sub graph, where I've taken out g and b, when I put back the match, when I add the part of g matching with b, it's a match for the whole graph. And that's how I get it. That completes the proof of Hall's theorem.