0:20

Hello everybody, welcome to our course in discrete mathematics,

and welcome to our second session on matchings and bipartite graphs.

Today, I will prove to you Hall's Theorem and

some other classic theorem from Graph Theory, which is called König's Theorem.

Let's quickly repeat the key notions from last time.

We defined what a matching is,

a matching is a set of edges here in this picture it's the blue edges.

And for a set of vertices on the left hand side of the bipartite graph,

we defined what the neighborhood is, gamma of A.

And for set A we defined the deficiency of A to be delta A,

which is A minus the size of it's neighborhood.

And delta of G is the maximum overall subset A on the left hand side.

And with this set up, we can state Hall's Theorem.

It has two parts, the easy and hard part.

The easy part says the matching cannot be bigger than U minus delta A.

And the hard part, that we're going to prove today, says you can't actually find

matching in a set where these two numbers match, but these two numbers are the same.

And put together, they form what you'll

normally read as Hall's Theorem in the literature.

Last time we also saw an algorithm for maximum matching, which drew heavily on

our machinery developed over the last couple of sessions, namely maximum flow.

Let's quickly go through it again.

So, you have a bipartite graph, you attach a source and

a sync vertex, and you find a maximum flow in your network,

the maximum integral flow, and then you can extract your maximum matching.

That an algorithm based on network flow.

All right, so, we know how to efficiently find a maximum matching.

And we know the easy part for theorem, and

we want to prove the hard part of Hall's Theorem today.

That's the problem for this session.

In order to do this, I want to introduce another important

concept of Graph Theory, and this is called vertex cover.

So again we have a graph for today, a bipartite graph.

And a vertex cover is a set of vertices that touches every edge.

Formally, that's a form of definition, so

let's now try to find a vertex cover in this graph.

For example, you could say, I take all the vertices on the left and

sure enough I touch every edge.

I can also take, All the vertices on

the left plus some vertices on the right, now I have a vertex cover of size 10 also.

But the interesting question, of course, is how many vertices do I really need?

For example in this graph, let's see, Which vertices should we choose.

3:56

So, the important theorem about vertex covers in bipartite graphs is called

König's Theorem.

And just like Hall's Theorem it comes with an easy part and a hard part.

The easy part says, if you have a vertex cover and the matching,

then the vertex cover must be at least as large as the matching.

And this is kind of easy to see if I have a matching like this, what is a matching?

A matching is a set of edges that don't touch each other.

And now I want to select a set of vertices that touches every edge.

Well, I also have to touch every edge in my matching, and

every vertex can only touch one of them, because they are disjoint, right?

So, you immediately see I need at least as many red vertices as I

have blue edges here.

5:08

Yeah, and where's our matching?

Let's find the matching of size, this edge,

maybe this edge, this edge, and this edge, right?

So, you see here we have a matching of size four and

you have a vertex cover of size four.

And this immediately implies that it's a minimum vertex cover in a maximum

matching.

So, now our goal is to prove the hard part of König's Theorem.

8:56

Because this edge goes from s to it's compliment, and

what is the capacity of these edges?

Well, we defined this to be infinity.

The edges that go between u and v in our flow network have capacity infinity.

But you know now, you see this is a contradiction,

because the capacity of s equals the size of the maximum matching and

the maximum matching cannot be larger than, for example, the set u.

So this is the clear contradiction,

that's marked kind of a big red arrow here,

that's a contradiction, unless we conclude for

all x in a and y in b minus b there is no edge xy.

10:45

So for example, edges like this, that go from

the source into here, they have capacity one,

and their total capacity is u without a, right?

So now, we don't have edges like this because our graph is bipartite, right?

And we don't have edges like this, and

we don't have edges like this, our above observation.

So, the remaining edges that go from s to its compliment are actually

edges going directly into t.

And how many are there?

Well, there will be many of them, and they all have capacity one.

And now you see here, very nice, the capacity of s is u minus a plus b,

which happens to be exactly the set, the size of all vertex covered.

And there you go, this proves the hard part of König's Theorem.

We constructed a matching and a vertex cover of the same size.

Great, but it's even better because now we can,

with no additional cost, actually finish the proof of Hall's Theorem.

12:08

Let's look for

a second at this fact here.

It tells you there is no edge from a to v without b.

In other words all the edges that go out of a are contained in b.

So in other words, the neighborhood of a is contained in b.

And with this fact, we can now lower bound the size of m as follows.

We have just calculated the size of m is u minus a plus b,

but now we know that b is larger than

the neighborhood of a, at least as large.

So, we get this is u minus a plus gamma of a,

and this is exactly u minus the deficiency of a.

And this, Is

exactly the hard part of Hall's Theorem.

We have a matching, and we have a set a, such that m is at least u minus delta m.

All right, to wrap up, here is König's Theorem that we just have proved,

and Hall's Theorem.

These are two classic theorems from Graph Theory.

The nice thing is, once you understand maximum flow, and

the maximum in Cut Theorem, both of these theorems follow more or less painlessly.

15:08

So you see here, already for the triangle, König's Theorem is not true anymore.

And this actually has a deeper reason that comes from Complexity Theory.

Let me tell you, so on the one hand side if we are in the general graphs,

we can still find a maximum matching in polynomial terms.

So, we have this algorithm, it's called Edmond's Blossom Algorithm,

which finds a maximum matching in general graphs.

But we don't know how to find a minimum vertex cover.

And most researchers actually believe that this is impossible,

because vertex cover is something that is called NP complete in Complexity Theory.

16:13

All right, actually you have to turn it the other way around.

The reason vertex cover, although it's NP complete for general graphs,

happens to be easy for bipartite graphs is because you have König's Theorem.

And König's Theorem tells you you can compute a maximum matching or

you can compute this maximum flow, and

then from this you can construct an optimal vertex cover.

So, in bipartite graphs we just are lucky by König's Theorem and

can find optimum vertex covers.