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 x_{1} y_{1} x_{2} y_{2} ... x_{k} where each y_{i} is matched to x_{i+1} and x_{1} is unmatched, there is some y_{k} out there that is not matched to any of the x_{i} but is adjacent to at least one of them (not necessarily x_{k}); if it's unmatched, we can extract an augmenting path by picking any x_{j} adjacent to y_{k} as the first edge, y_{j-1} as the next edge, and then continuing to work backwards in the same way until we get to x_{1}; if it's matched, then we let x_{k+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.

A working proof can now be found on the BipartiteGraphs page or in ยง17.4 of BiggsBook.