Problem
COM-B2-M08-P014 Unequal Degree Bounds
#14
★★★★☆ Level 4 of 5
In a bipartite graph, every left vertex has degree at least \(5\), and every right vertex has degree at most \(4\). Prove that there is a matching covering the left part.
Counting gives even \(|N(S)|\ge \frac54|S|\).
For any left-side set \(S\), at least \(5|S|\) edges leave it. All enter \(N(S)\), and each right-side vertex receives at most \(4\) such edges. Thus \(5|S|\le4|N(S)|\), so \(|N(S)|\ge \frac54|S|\ge |S|\).
By Hall's theorem, there is a matching covering the left part.
A good olympiad version of degree counting.