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.