Finding a subset in bipartite graph violating Hall's condition
Let $G=(X,Y,E)$ be a bipartite graph with $|X|=|Y|=n$ having a maximum matching $M$. Consider the directed graph $G'$ on the vertex set $X \cup Y$ which includes the edges of $G$ oriented from $X$ to $Y$ and the edges of $M$ oriented from $Y$ to $X$. Let $U \subseteq X$ be the set of vertices of $X$ unmatched in $M$, and let $S$ be the set of vertices reachable from $U$ in $G'$. Then $|N(S \cap X)| = |S \cap X| - (n-|M|)$.

For the proof, let us first notice that $|N(S \cap X)| \geq |S \cap X| - (n-|M|)$, since otherwise each matching would have to miss more than $n-|M|$ vertices of $S \cap X$. It remains to show that $|N(S \cap X)| \leq |S \cap X| - (n-|M|)$. The idea is to show that $|X \setminus S| + |S \cap Y| \leq |M|$. Given this, note that by definition $N(S \cap X) = S \cap Y$, and so
$$ |N(S \cap X)| = |S \cap Y| \leq |M| - |X \setminus S| = |M| - (n-|S \cap X|) = |S \cap X| - (n-|M|). $$

To finish the proof, we show that $|X \setminus S| + |S \cap Y| \leq |M|$. We do this by showing that each vertex in both of these sets belongs to $M$. For each $(x,y) \in M$, if $y \in S$ then $x \in S$, showing that at most one vertex is counted in $|X \setminus S| + |S \cap Y|$ for each edge in the matching, proving the inequality. It is clear that each vertex in $X \setminus S$ belongs to $M$, since by definition unmatched vertices belong to $S$. The crux of the proof is showing that each vertex in $S \cap Y$ belongs to $M$. Indeed, if some $y \in S \cap Y$ didn't belong to $M$, then the path proving that $y \in S$ is an augmenting path for the matching: if we remove all edges going from $Y$ to $X$ on the path and replace them by all edges going from $X$ to $Y$ on the path then we obtain a matching with one more edge than before. Since we assumed that $M$ is a maximum matching, this is impossible, completing the proof.