📐 Hall

A bipartite graph $G$ with bipartition $(X, Y)$ has a matching saturating $X$ if and only if $|N(S)| \\geq |S|$ for all $S \\subseteq X$.

Proof: Necessity is clear. For sufficiency, induct on $|X|$. If $|N(S)| > |S|$ for all proper $S$, match any $x \\in X$ to a neighbor and apply induction. Otherwise, some $S$ has $|N(S)| = |S|$; by induction match $S$ to $N(S)$. Hall\

From: Introduction to Graph Theory

Learn more: https://west-graphs-deploy.vercel.app/#/section/8

Explore all courses: https://mathacademy-cyan.vercel.app