## Lecture Eleven: Matching

• The fundamental theorem about unweighted bipartite matching is Hall' theorem: a bipartite graph (X,Y,E) has a complete match(i.e. a match in which all of X participates) if and only if for every non-empty subset A of X, R(A), its range in Y, satisfies |A| <=|R(A)|.

• There's a picture proof - in textbook - using flows. Theorem can also be proved by induction on the size of X. Clearly true for base case |X| = 1. Now two parts of induction proof: for all non-empty A, |A| < |R(A)| (strict inequality)! (pf here easy: just strip off any e from x to y); and there exists non-empty proper A for which |A| = |R(A)|. Second case more subtle. By induction, there's a complete match on A to its range. Throw that out. Look at what's left. It smaller, so there's a complete match for the leftovers if for all B subset of leftovers, |B| <= |R(B)|. Punch line: if this fails, that is if for some B |B| > |R(B)|, then B in the original graph must be sending some edges into R(A), and indeed |A+B| > |R(A+B)|, a contradiction.

• Corollary. If deg(x) for all x in X is >= k, deg(y) for all y in Y is <= k, then there is a complete match.

• After we worked out this proof, we did some examples, such as "Every Latin Rectangle can be extended to a Latin Square", and "if all girls at a school have k possible boyfriends, and all boys have k possible girlfriends, then a dating arrangement is possible!"
-- RobbieMoll - 17 Oct 2006
Topic revision: r1 - 2006-10-17 - RobbieMoll    Copyright © 2008-2019 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding UMass CS EdLab? Send feedback