BipartiteGraphs and matchings. Readings: Sections 17.1, 17.4, and 17.5. Click on the date for notes on the error in lecture.
If you attended lecture and are wondering how to make the augmenting path construction actually work (since it didn't), the trick is that Hall's condition gives us that for any sequence x1 y1 x2 y2 ... xk where each yi is matched to xi+1 and x1 is unmatched, there is some yk out there that is not matched to any of the xi but is adjacent to at least one of them (not necessarily xk); if it's unmatched, we can extract an augmenting path by picking any xj adjacent to yk as the first edge, yj-1 as the next edge, and then continuing to work backwards in the same way until we get to x1; if it's matched, then we let xk+1 be its match and keep going. The working-backwards step was where I got confused, since at that point we don't need Hall's condition any more and I kept thinking we did.