Matchings in Bipartite Graphs: Hall's and König's Theorem

Loading...

From the course by Shanghai Jiao Tong University

Discrete Mathematics

60 ratings

Shanghai Jiao Tong University

Discrete Mathematics

60 ratings

Discrete mathematics forms the mathematical foundation of computer and information science. It is also a fascinating subject in itself. Learners will become familiar with a broad range of mathematical objects like sets, functions, relations, graphs, that are omnipresent in computer science. Perhaps more importantly, they will reach a certain level of mathematical maturity - being able to understand formal statements and their proofs; coming up with rigorous proofs themselves; and coming up with interesting results. This course attempts to be rigorous without being overly formal. This means, for every concept we introduce we will show at least one interesting and non-trivial result and give a full proof. However, we will do so without too much formal notation, employing examples and figures whenever possible. The main topics of this course are (1) sets, functions, relations, (2) enumerative combinatorics, (3) graph theory, (4) network flow and matchings. It does not cover modular arithmetic, algebra, and logic, since these topics have a slightly different flavor and because there are already several courses on Coursera specifically on these topics.

From the lesson

Matchings in Bipartite Graphs

We prove Hall's Theorem and Kőnig's Theorem, two important results on matchings in bipartite graphs. With the machinery from flow networks, both have quite direct proofs. Finally, partial orderings have their comeback with Dilworth's Theorem, which has a surprising proof using Kőnig's Theorem.

Matchings in Bipartite Graphs: Hall's and König's Theorem16:59

Meet the Instructors

Dominik Scheder
Assistant Professor
The Department of Computer Science and Engineering

[MUSIC]

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.

I could, for example, choose these four vertices.

And you can check that this is really a vertex cover of size four, and

let's see whether this is optimal or whether we can do something better.

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.

The hard part of König's Theorem says that these two numbers can actually match.

So, if you find an optimal vertex cover and an optimal matching,

their sizes will be equal.

For example, in this graph up here, that's our vertex cover.

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.

First of all, if you combine these two, the version you find Konig's Theorem in

the literature to usually is in the following form here.

In a bipartite graph the maximum matching has the same size as the minimum

vertex cover.

Also note that here I forgot, so

its König's Theorem not Konick's Theorem or something.

Good, let's try to prove the hard part.

So, what do we want to do?

We want to find a vertex cover and a matching of same of size.

Let's try.

So, here's our bipartite graph, and just as in the algorithm,

I add a source vertex s, and a sync vertex t.

Okay.

So, if you remember the algorithm,

the algorithm actually was to search for a maximum flow.

Maximum integral flow.

And then you can immediately extract the matching from it.

So, the maximum matching has the same size as the maximum flow.

All right, so what do we know about maximum flow?

Well, we know the max flow in Cut Theorem.

So, we know that this equals the capacity of a minimum cut.

A minimum st cut.

This is a fact that we just import, that we take from two lectures ago,

three lectures when you proved it, and we are going to apply it today.

So, s is an st cut, which means that s contains the source, but not the sync.

So, it must somehow look like this.

That's our set s, the minimum cut.

Now consider this set here and call it a, and this set here and call it b.

So formally, a is s intersect u,

and b is s intersect v, and

here comes a key observation.

Suppose you have a vertex x here and a vertex y here,

so what happens if you have an edge from x to y?

So, if xy is an edge, Well,

then the capacity of your cut, Must be at least the capacity of this edge, right?

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.

In other words, U without a,

together with b, is a vertex cover.

Right? It's a vertex cover

of your bipartite graph.

Let's give it a name, c.

And what is the size of c?

The size of C,

it's u without a plus b.

So, let's compare this to the size of our matching.

As we have seen, the size of the matching equals the value of the maximum flow,

which by the Maximum and Cut Theorem, equals the capacity of the cut.

And what is the capacity of the cut?

For this we have to look at the edges that go from s to its complement.

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.

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.

And actually, if you look into the literature on Wikipedia or anywhere,

in most cases, Hall's Theorem is stated a little bit different.

It's stated like this, if every set a has a neighborhood gamma

of a that is at least as large as a, then you find a matching of size u.

That's how it's usually stated.

You can think about it,

it is actually equivalent to the version of Hall's Theorem as we stated it here.

And one last thing, we talked only about bipartite graphs here, and

for a good reason, because in general graphs König's Theorem is simply not true.

Let me give you an example.

Here is a non bipartite graph.

And if I ask you, what is the maximum matching?

It's obviously one, because you can choose at most one edge.

How about vertex cover?

The smallest vertex cover has size two,

because you have to select at least two vertices.

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.

And right, I mean most people are very pessimistic about NP complete problems and

don't believe that we'll ever find an efficient algorithm for these problems.

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.

All right, that's it for today, thanks.

[MUSIC]

Explore our Catalog

Join for free and get personalized recommendations, updates and offers.

Coursera provides universal access to the world’s best education, partnering with top universities and organizations to offer courses online.

© 2018 Coursera Inc. All rights reserved.

Download on the App Store

Get it on Google Play