What are Hall's Theorem and Hall's Condition for bipartite matchings in graph theory? Also sometimes called Hall's marriage theorem, we'll be going it in today's video graph theory lesson!

A bipartite graph with partite sets U and W, where U has as many or fewer vertices than W, satisfies Hall's condition if, for every subset S of U, S has as many or fewer vertices than it has neighbors (note that all of S's neighbors are in W, since this is a bipartite graph).

Now let G be a bipartite graph with partite sets U and W, where |U| is less than or equal to |W|. Hall's theorem states that G contains a matching that covers U if and only if G satisfies Hall's condition.

Lesson on matchings:    • Matchings, Perfect Matchings, Maximum...  
Proof of Hall's theorem:    • Proof: Hall's Marriage Theorem for Bi...  

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