Graph Theory, Lecture 6: Matching in bipartite graphs

Alternating and augmenting paths vs greedy algorithm.
König's Theorem 2.1.1 (13:00) with proof, slowly developed (from 24:40).
Standard cardinality version vs structural version.
Duality aspects (from 16:25): necessary vs sufficient conditions;
obvious inequality has an instance with equality;
obvious potential obstruction to an existence statement always exists;
existence of dual certificates; good characterisations, NP vs coNP.
Hall's Marriage Theorem 2.1.2 (from 37:25) with two proofs,
slowly developed (from 42:20 and 51:15, resp.). Note 2nd proof's technique:
identify a subgraph where the condition holds 'only just'; split
the problem into two smaller problems there; combine their solutions.
Duality aspects as earlier. Covers most of Chapter 2.1.