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₁ y₁ x₂ y₂ ... x_k where each y_i is matched to x_i+1 and x₁ 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₁; 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.