Proof. Since no sdr can be larger than this minimum value, it suffices to show that we can find an sdr whose size is this minimum. The proof is by induction on $n$; the case $n=1$ is easy.

Suppose first that the minimum value is $n$, so that for all $k$ and all collections of sets $A_{i_1},A_{i_2},\ldots,A_{i_k}$, $$n-k+|\bigcup_{j=1}^k A_{i_j}|\ge n.$$ Then rearranging we see that $$|\bigcup_{j=1}^k A_{i_j}|\ge k,$$ so by Hall's Theorem (4.1.1), there is an sdr of size $n$.

Note that the minimum value of $n-k+|\bigcup_{j=1}^k A_{i_j}|$ occurs when $|\bigcup_{j=1}^k A_{i_j}|-k$ is a minimum, that is $$\min(n-k+|\bigcup_{j=1}^k A_{i_j}|)= n+\min(|\bigcup_{j=1}^k A_{i_j}|-k).$$ Suppose now that the minimum $m$ is less than $n$, and that $m=n-k+|\bigcup_{j=1}^k A_{i_j}|$, with $0< k< n$. Let $B_j=A_{i_j}$; since $k< n$, the induction hypothesis applies to the sets $B_1,\ldots,B_k$. Since each set $B_j$ is $A_{i_j}$, $|\bigcup_{j=1}^l B_{h_j}|-l\ge |\bigcup_{j=1}^k A_{i_j}|-k$, for all $l$ and $B_{h_1},\ldots,B_{h_l}$. Thus, the minimum value of $|\bigcup_{j=1}^l B_{i_j}|-l$, over all $l$ and $B_{h_1},\ldots,B_{h_l}$, is $|\bigcup_{j=1}^k B_{j}|-k=|\bigcup_{j=1}^k A_{i_j}|-k$, so by the induction hypothesis, the sets $A_{i_1},A_{i_2},\ldots,A_{i_k}$ have an sdr of size $k-k+|\bigcup_{j=1}^k A_{i_j}|=|\bigcup_{j=1}^k A_{i_j}|=m-n+k$, $\{x_1,\ldots,x_{m-n+k}\}$.

Now consider the $n-k$ sets consisting of those original sets not in $A_{i_1},A_{i_2},\ldots,A_{i_k}$, that is, $\{A_i\mid i\notin\{i_1,\ldots,i_k\}\}$. Let $C_i=A_i\backslash \bigcup_{j=1}^k A_{i_j}$ for $i$ not in $i_1,i_2,\ldots,i_k$. Consider some sets $C_{g_1},C_{g_2},\ldots,C_{g_l}$. If $|\bigcup_{j=1}^l C_{g_j}|< l$ then $|\bigcup_{j=1}^l C_{g_j}|-l< 0$ and $$\eqalign{ n-k+|\bigcup_{j=1}^k A_{i_j}| &> n-k-l+|\bigcup_{j=1}^l C_{g_j}|+|\bigcup_{j=1}^k A_{i_j}|\cr &\ge n-(k+l)+|C_{g_1}\cup\cdots\cup C_{g_l}\cup A_{i_1}\cup\cdots \cup A_{i_k}|\cr &= n-(k+l)+|A_{g_1}\cup\cdots\cup A_{g_l}\cup A_{i_1}\cup\cdots \cup A_{i_k}|,\cr }$$ contradicting the fact that $n-k+|\bigcup_{j=1}^k A_{i_j}|$ is a minimum. Thus by Hall's Theorem (4.1.1), the sets $C_{g_1},C_{g_2},\ldots,C_{g_{n-k}}$ have a complete sdr $\{y_1,\ldots,y_{n-k}\}$. By the definition of the sets $C_i$, $\{x_1,\ldots,x_{m-n+k}\}\cap\{y_1,\ldots,y_{n-k}\}=\emptyset$, so $\{x_1,\ldots,x_{m-n+k}\}\cup \{y_1,\ldots,y_{n-k}\}$ is an sdr of size $m-n+k+n-k=m$ as desired.

Finally, suppose that the minimum value of $n-k+|\bigcup_{j=1}^k A_{i_j}|$ occurs only when $k=n$, so we want an sdr of size $$ n-n+|\bigcup_{j=1}^n A_{j}|=|\bigcup_{j=1}^n A_{j}|.$$ Then $$\eqalign{ n-(n-1)+|\bigcup_{j=1}^{n-1} A_{j}|&>|\bigcup_{j=1}^n A_{j}|\cr 1+|\bigcup_{j=1}^{n-1} A_{j}|&>|\bigcup_{j=1}^n A_{j}|\cr |\bigcup_{j=1}^{n-1} A_{j}|&\ge|\bigcup_{j=1}^n A_{j}|.\cr }$$ Since $|\bigcup_{j=1}^{n-1} A_{j}|\le|\bigcup_{j=1}^n A_{j}|$, $|\bigcup_{j=1}^{n-1} A_{j}|=|\bigcup_{j=1}^n A_{j}|$. By the induction hypothesis, the theorem applies to the sets $A_1,A_2,\ldots,A_{n-1}$. If the minimum of $(n-1)-l+|\bigcup_{j=1}^l A_{i_j}|$ occurs when $l=n-1$, then there is an sdr of size $(n-1)-(n-1)+|\bigcup_{j=1}^{n-1} A_{j}| =|\bigcup_{j=1}^{n-1} A_{j}| =|\bigcup_{j=1}^{n} A_{j}|$, as desired.

If the minimum occurs when $l< n-1$ and not when $l=n-1$, then $$\eqalign{ (n-1)-l+|\bigcup_{j=1}^{l} A_{i_j}|< |\bigcup_{j=1}^{n-1} A_{j}|\cr n-l+|\bigcup_{j=1}^{l} A_{i_j}|< |\bigcup_{j=1}^{n-1} A_{j}|+1\cr }$$ and by assumption $$ n-l+|\bigcup_{j=1}^{l} A_{i_j}|>|\bigcup_{j=1}^{n} A_{j}|.$$ Thus $$\eqalign{ |\bigcup_{j=1}^{n} A_{j}|&< n-l+|\bigcup_{j=1}^{l} A_{i_j}|\cr &< |\bigcup_{j=1}^{n-1} A_{j}|+1\cr &=|\bigcup_{j=1}^{n} A_{j}|+1.\cr }$$ This means that there is an integer strictly between two consecutive integers, a contradiction. This completes the proof. $\qed$