Proof: Hall's Marriage Theorem for Bipartite Matchings | Graph Theory

A bipartite graph G with partite sets U and W, where |U| is less than or equal to |W|, contains a matching of cardinality |U|, as in, a matching that covers U, if and only if for every subset S of U, |S| is less than or equal to the cardinality of the neighborhood of S (as in - S has as many or fewer vertices than it has neighbors). This is Hall's theorem for bipartite matchings, also called Hall's marriage theorem. We prove the theorem in today's video graph theory lesson!

The first direction of the proof is a breeze! Then we use strong induction and cases to prove the other direction! It's a lot of fun!

Lesson on Hall's theorem and Hall's condition:    • Hall's Theorem and Condition for Bipa...  
Lesson on matchings:    • Matchings, Perfect Matchings, Maximum...  
Lesson on vertex-induced subgraphs:    • What is a Vertex Induced Subgraph? | ...  

I think those are all the links I promised in the lesson. Let me know if I missed one!

I hope you find this video helpful, and be sure to ask any questions down in the comments!

+WRATH OF MATH+

◆ Support Wrath of Math on Patreon:   / wrathofmathlessons  

Follow Wrath of Math on...
● Instagram:   / wrathofmathedu  
● Facebook:   / wrathofmath  
● Twitter:   / wrathofmathedu  

My Music Channel:    / seanemusic