English translation of a page from
DISKRETE MATHEMATIK
Erich Prisner
Matchings in Bipartite Graphs
Example
In a small village, 11 inhabitants are
members in clubs, and there are 9 such clubs.
A, C, I and J are members of the pigeon breeders association.
B, D, I and K form the train lovers club.
C, E and F are the stamps collector club.
A, E, H and their cars form the old car lovers club.
B, H and J form the local bingo association.
E, F and G are the soccer socks,
and E, F, G, H are the football foxes.
F, G und H form the local choir, presently only a trio,
and finally E, F, G and H are the computer club.
(a) There is a meeting scheduled to discuss the possibility
of building a common club house. Each club has to send one
representative, but certainly nobody should speak for two
or more clubs at that meeting. Is that possible at all?
(b) One day before the meeting, G is going on a business trip to Europe.
Is the meeting still possible, maybe with different representatives?

Try it!
By clicking on the circles you select or deselect a representative.

Terminology
A bigraph models situations, where we have an
arbitrary relation R
Í A × B between
disjoint sets A and B. By defining V := A
È B and
Adj = {(a,b), (b,a) / a
Î A, b Î B, (a,b) Î
R} , we get the already mentioned concept of
bipartite
graphs. These special graphs are the
bigraphs. Instead of R, we will work in
the following either with the ireflexive symmetric relation
Adj on V = A È
B, or with the edge set
E. So let G = (V,E) a bipartite graph with bipartition V = A È B. We define:
 A subset E' of the
edge set E of a graph G=(V,E) is
 a matching,
if no two of these E'edges have a common vertex, i.e. if each vertex
occurs in at most one of these E'edges,
 a EVcovering,
if every vertex occurs in at least one of these E'edges.
 A subset V' of the vertex set V is
 independent,
if no two of these V'vertices are adjacent, i.e. if each edge contains
at most one of these V'vertices,
 a VEcovering,
if every edge contains at least one of these V'vertices.

It's easy to find small matchings or independent sets,
and large EV or VEcoverings, but in contrast to this,
we are interested in maximum
matchings or independent vertex sets,
and in minimum EV or VEcoverings.
These structures are called optimal.
The sizes of the corresponding optimal sets are denoted by
m, c_{EV}, æ, c_{VE}.
Constructions
We need a lemma on the structure of minimum EVcoverings (1),
and several constructions (2.6.), transforming
optimal sets into optimal sets:

Stars in c_{EV} :
Let’ start with some minimum EVcovering E'.
No adjacent vertices have (V,E')degree larger than 1,
otherwise the edge between them would be superfluous,
contradicting the minimum property E'.
Therefore (V,E') is the disjoint union of stars,
where a star is a tree with at least 2 vertices, containing a
central vertex and all other vertices adjacent to this central
vertex.
Each component of (V,E') is a tree, has thus one edge less
than vertices. Thus the number of components of
(V,E') equals V  E'.

æ c_{VE} :
If W is a (maximum) independent vertex set,
then its complement V \ W is a (minimum) vertex edge covering,
and conversely.

c_{EV} ® æ :
Let E' be a minimum edge vertex covering.
We concentrate on the set W
of all vertices covered by exactly one E'edge,
but whose (unique) E'neighbor is covered by more than
one E'edge. Note that W is independent.
Now we are going to increase W, but keeping the
independece property.
We cannot add neighbors of W to W without violating
this independence property, but we can add all
E'neighbors of the Eneighbors of the vertices of W.
By repeatedly extending W in this way, we finally arrive
at some maximal independent set. It can be shown that
the resulting set is even a maximum independent set.

æ ® c_{EV} :
Choose a maximum independent vertex set W.
For each member w of W we choose some neighbor f(w),
if possible distinct from the previously chosen vertices
f(u) so far. Then the set E' of all edges between w and f(w),
for w Î W, forms a edgevertex
covering. It can even be shown that this covering is minimum.

c_{EV} ® m :
Let E' be a minimum edgevertex covering. It has the star shape
described under (1) above. By choosing one edge out of every
star component, we get obviously a matching. Again it can be shown
that the resulting matching is maximum.

m ® c_{EV} :
Let E' be a maximum matching. For every vertex x
which is not covered by E' we choose any neighbor f(x).
All these edges xf(x), x Î V \ V(E'),
is a edgevertex covering, and it can again be shown that
it is minimum.
Theorems
(2.) implies the equality æ = V  c_{VE}.
(3.) and (4.) together imply
æ = c_{EV} for finite bipartite graphs.

This equality also follows by
Dilworth's Theorem
(
We define a order relation on V by
a £ b if [a=b or
(a Î A, b Î B,
and {a,b} Î E(G))].
The independent sets in G are exactly the
antichains in (V,£),
whereas each edgevertex coverings of G corresponds
a partition of V by
(V,£)chains.
).
(1.), (5.) and (6.) imply m = V  c_{EV} in bipartite graphs.
Overall we get:
König's Theorem (1931)
The size of a minimum VEcovering c_{VE}
equals the size m of a maximum
matching in every finite bipartite graph.

Philip Hall'sTheorem (1935)

marriage version:
Let G be a finite bipartite graph with bipartition
V = A È B.
There is some matching of
cardinality A if and only if for every integer k,
any k elements of A have at least k neighbors in B.
 version using representatives:
A system of distinct representatives of a family of sets
{M_{i}/i Î I}
is any onetoone function
Funktion f: I ®
È_{iÎ I}
M_{i},
where each
f(i) is an element of M_{i} for each i.
A family of sets has such a system of distinct representatives
if and only if we get
 È_{j
Î J} M_{j} 
³ J
for every subset J of I.

Proof:
One direction is easy: If there is such a (bad) subset A' of A
obeying N_{G}(A') < A', no matching can contain all vertices of A'
whence there is no matching of cardinality A.
If conversely there is no matching of cardinality A,
then König's Theorem above implies c_{VE} < A.
Let V' be a minimum vertexedge covering, V' = c_{VE}
Dann liegt jeder Nachbar jeder Ecke von A \ V' in
B Ç V', also
N_{G}(A \ V') Í
B Ç V', also
N_{G}(A \ V') £
B Ç V' =
V'  A Ç V' = A \ V'.

Exercise:
For integers n and k, k £ n/2,
let A denote the set of all (k1)element subsets
of {1,2,...,n}, whereas
B denotes the set of all kelement subsets
of {1,2,...,n}.
By calling
X Î A and
Y Î B adjacent
if X Í Y,
we get a bipartite graph with
sets A and B.
Use Hall's Theorem to show that this graph has
a (perfect) matching of size A.
Exercise:
Prove
Sperner's Theorem, using Hall's Theorem.
How to find maximum matchings  augmenting paths
The simplest idea is to start with any matching and to successively add
edges as long as possible. Unfortunately we may get in a dead end in this way. In
the example to the left, it is impossible to add any edge without violating the
matching property, but nevertheless the matching is still not maximum, as we
will see.
The outlet for this dead end is the idea of augmenting paths.
A path x_{0}, y_{0}, x_{1}, y_{1}, ... ,
x_{k}, y_{k} is augmenting with respect to a given
matching M, if neither x_{0} nor y_{0}
are covered by an edge of M, and the edges of the path alternatingly
lie in M, i.e. y_{0}x_{1}, y_{1}x_{2}, ...
y_{k1}x_{k} are in M.
If we have found such an augmentig path, we replace the (k) Medges on it
by the (k+1) nonMedges to get another matching containing exactly one edge more.
What if we don't find such an augmenting path. If there is none left,
do we need another tool, to increase the matching? Surprisingly not!
Every matching where there is no
augmenting path (with respect to that matching) is maximum.
In the applet to the left you may try to find augmenting paths (blue)
and successively increase the size of the matching.
How to find maximum matchings  augmenting trees
How do we find augmenting paths in a systematical way?
Assume we have a matching M and a vertex x not covered by M.
Note that all augmenting paths start and end
at such notyet covered vertices.
Let's try to find all augmenting paths starting at x,
so x is our first vertex x_{0}.
All neighbors of x could be y_{0} we call these vertices
the children of x.
Such a child y_{0} is either not covered by M (then we
have already found our alternating path) or it is covered.
In the second case,
the unique Mneighbor of it must be our x_{1},
and is called the child of y_{0}.
All further neighbors of x_{1} are candidates for y_{1},
but again, every such y_{1} is either not covered by M
(then we may stop again) or has a unique child x_{2}.
Since at each point we only have to check vertices not yet on
our tree, we obtain a tree structure by proceeding.
Although it may or may not contain an augmenting path,
we call it the augmnenting tree starting at x
(wishful thinking).
All we have to do is to generate and check all augmenting trees
for all our notyet covered vertices x.
In the applet to the right you may do exactly this by clicking on
notyet covered vertices. The resulting augmenting tree is shown in red,
and if it contains an augmenting path, one of them is colored blue.
You may experiment with more augmenting trees and paths
in a larger Applet.
You may also get the answer to our initial example
(with G in Europe) there; the situation is modelled by Graph D there.
Erich Prisner, October 2000.