Bipartite graphs, maximum size matchings, Hall's condition

Question

Suppose that $G(U,W)$ is a bipartite graph. Show that if $$d:= \max \{|S|-|T_s|: S \subseteq U \} \geq 0,$$ where $T_s = \{ w \in W: w \: \text{adjacent to some} \: s \in S\},$ then a maximum size matching in $G(U,W)$ has size $|U| -d$.

I've noticed that the case $d=0$ is Hall's condition, as we can take $S = \emptyset$.

But I'm not too sure how to prove the thing they're asking

Answer 1

Hint:

• Create graph $G'$, that is, to the set $W$ add $d$ dummy vertices, each connecting to all the vertices of $U$.
• In this modified graph you have $d'=0$, so by Hall's theorem there is a matching of size $|U|$, but at most $d$ edges can match dummy vertices.

I hope this helps $\ddot\smile$