Problem
COM-B2-M08-P007 Large Left Degrees
#7
★★★☆☆ Level 3 of 5
In a bipartite graph, every left vertex has degree at least \(3\), and every right vertex has degree at most \(3\). Prove that there is a matching covering the whole left part.
For \(S\) on the left, count edges from \(S\) to \(N(S)\).
Take any \(S\) in the left part. At least \(3|S|\) edges leave \(S\). All enter \(N(S)\), and each vertex of \(N(S)\) receives at most \(3\) such edges. Thus \(3|S|\le3|N(S)|\), so \(|N(S)|\ge |S|\).
Hall's condition holds, hence there is a matching covering the left part.
Template: Hall by edge counting.