Source of problem: Janson, Łuczak, and Ruciński, section 4.1 (page 82, line -10).
The question:
Let $G = (V_1 \cup V_2, E)$ be a bipartite graph with $|V_1| = |V_2| = n$ and no perfect matching. By Hall's matching theorem, there is a set $S \subseteq V_i$ (for $i=1$ or $2$) such that $|N(S)|<|S|,$ where $N(\cdot )$ is the neighborhood in the graph $G$. Suppose $S$ is a minimal such 'Hall Violator'. Is it true that $|S| \leq \lceil \frac{n}{2} \rceil$? If so, why?
My thinking so far:
Based on my reading about minimal Hall violators, it may be useful to fix a maximal matching in $G$; this partitions $V_1$ and $V_2$ into 'matched' sets $A_1, A_2$ of size $m < n$ and 'unmatched' sets $B_1, B_2$ of size $n-m.$
It is also notable that the condition depends on the parity of $n,$ giving a hint as to why it might be true. It is easy to show that if $S$ is a minimal Hall violator, then $|S| = |N(S)|+1.$ If we could then show that $|S| + |N(S)| \leq n,$ this translates to
$$2|S|-1 \leq n$$
$$\iff |S| \leq \frac{n+1}{2}.$$
Since $|S|$ is an integer, this translates to $|S| \leq \lceil \frac{n}{2} \rceil.$
As mentioned, it suffices to prove $|N(S)| + |S| \leq n.$
We show something weaker--not that $|S| \leq \lceil \frac{n}{2} \rceil$ for any minimal Hall violator, but rather that there exists a minimal Hall violator $S'$ with $|N(S')| + |S'| \leq n.$
Let $S \subset V_1$ be a minimal Hall violator.
Notice that $(|N(S)| + |S|) + (|V_2 \setminus N(S)| + |V_1 \setminus S|) = 2n.$ Thus one of these terms is $\leq n.$ But $N(V_2 \setminus N(S)) \subseteq V_1 \setminus S,$ so either $|N(S)| + |S| \leq n$ (in which case we're done!), or if that fails then $|V_2 \setminus N(S)| + |N(V_2 \setminus N(S))| \leq n$, so we can take a minimal Hall violator $S' \subseteq V_2 \setminus N(S)$, and $|S'| + |N(S')| \leq |V_2 \setminus N(S)| + |N(V_2 \setminus N(S))| \leq n.$