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. Unfortunately your browser doesn't show applets.

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 E-V-covering, 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 V-E-covering, if every edge contains at least one of these V'-vertices.

It's easy to find small matchings or independent sets, and large E-V- or V-E-coverings, but in contrast to this, we are interested in maximum matchings or independent vertex sets, and in minimum E-V- or V-E-coverings. These structures are called optimal. The sizes of the corresponding optimal sets are denoted by m, cEV, æ, cVE.

Constructions

We need a lemma on the structure of minimum E-V-coverings (1), and several constructions (2.-6.), transforming optimal sets into optimal sets:

  1. Stars in cEV : Let’ start with some minimum E-V-covering 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'|.
  2. æ cVE : If W is a (maximum) independent vertex set, then its complement V \ W is a (minimum) vertex edge covering, and conversely.
  3. cEV ® æ : 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 E-neighbors 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.
  4. æ ® cEV : 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 edge-vertex covering. It can even be shown that this covering is minimum.
  5. cEV ® m : Let E' be a minimum edge-vertex 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.
  6. m ® cEV : 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 edge-vertex covering, and it can again be shown that it is minimum.

You may want to try these constructions in an for different bipartite graphs.

Theorems

(2.) implies the equality æ = |V| - cVE.
(3.) and (4.) together imply

æ = cEV 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 edge-vertex coverings of G corresponds a partition of V by (V,£)-chains. ).
(1.), (5.) and (6.) imply m = |V| - cEV in bipartite graphs.
Overall we get:

König's Theorem (1931) The size of a minimum V-E-covering cVE 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 {Mi/i Î I} is any one-to-one function Funktion f: I ® ÈiÎ I Mi, where each f(i) is an element of Mi for each i. A family of sets has such a system of distinct representatives if and only if we get | Èj Î J Mj | ³ |J| for every subset J of I.
Proof: One direction is easy: If there is such a (bad) subset A' of A obeying |NG(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 cVE < |A|. Let V' be a minimum vertex-edge covering, |V'| = cVE Dann liegt jeder Nachbar jeder Ecke von A \ V' in B Ç V', also NG(A \ V') Í B Ç V', also
|NG(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 (k-1)-element subsets of {1,2,...,n}, whereas B denotes the set of all k-element 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 x0, y0, x1, y1, ... , xk, yk is augmenting with respect to a given matching M, if neither x0 nor y0 are covered by an edge of M, and the edges of the path alternatingly lie in M, i.e. y0x1, y1x2, ... yk-1xk are in M. If we have found such an augmentig path, we replace the (k) M-edges on it by the (k+1) non-M-edges 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 not-yet covered vertices. Let's try to find all augmenting paths starting at x, so x is our first vertex x0. All neighbors of x could be y0--- we call these vertices the children of x. Such a child y0 is either not covered by M (then we have already found our alternating path) or it is covered. In the second case, the unique M-neighbor of it must be our x1, and is called the child of y0. All further neighbors of x1 are candidates for y1, but again, every such y1 is either not covered by M (then we may stop again) or has a unique child x2. 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 not-yet covered vertices x.

In the applet to the right you may do exactly this by clicking on not-yet 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.