[proofplan]
We reduce the problem to [Hall's Marriage Theorem](/theorems/2018) by constructing an auxiliary bipartite graph. The family $\mathcal{A} = \{A_1, \ldots, A_m\}$ becomes the left vertex class, the ground set $\bigcup_{i=1}^m A_i$ becomes the right vertex class, and edges encode membership. A complete matching in this bipartite graph is exactly a system of distinct representatives, and Hall's condition for the graph is exactly the union condition in the theorem statement.
[/proofplan]
[step:Construct the auxiliary bipartite graph encoding set membership]
Define a bipartite graph $G = (X, Y; E)$ as follows. Set
\begin{align*}
X &= \{A_1, \ldots, A_m\}, \\
Y &= \bigcup_{i=1}^{m} A_i,
\end{align*}
and place an edge from $A_i \in X$ to $y \in Y$ whenever $y \in A_i$.
[guided]
The idea is to encode the membership relation as a bipartite graph. The left side $X$ consists of the sets $A_1, \ldots, A_m$ themselves (viewed as abstract vertices, one per set in the family). The right side $Y$ is the ground set $\bigcup_{i=1}^m A_i$ containing all elements that appear in at least one member of $\mathcal{A}$. We connect $A_i$ to $y$ precisely when $y \in A_i$, so the neighbourhood of $A_i$ in $G$ is exactly the set $A_i$ viewed as a subset of $Y$.
[/guided]
[/step]
[step:Identify complete matchings with systems of distinct representatives]
A complete matching from $X$ to $Y$ is an injection $f: X \to Y$ with $A_i f(A_i) \in E$ for every $i$. By construction of $G$, the edge condition $A_i f(A_i) \in E$ means $f(A_i) \in A_i$. Injectivity of $f$ means $f(A_1), \ldots, f(A_m)$ are distinct. Setting $a_i := f(A_i)$, we obtain distinct elements $a_1, \ldots, a_m$ with $a_i \in A_i$ for each $i$, which is precisely a system of distinct representatives for $\mathcal{A}$.
Conversely, any SDR $a_1, \ldots, a_m$ defines a complete matching $f(A_i) = a_i$.
[guided]
We verify that the two notions coincide exactly.
**Matching implies SDR.** Suppose $f: X \to Y$ is a complete matching. For each $i \in \{1, \ldots, m\}$, the edge condition says $f(A_i) \in A_i$ (the chosen representative lies in the set). Injectivity says $f(A_i) \neq f(A_j)$ whenever $i \neq j$ (the representatives are distinct). So $a_i := f(A_i)$ gives an SDR.
**SDR implies matching.** Conversely, given distinct elements $a_1, \ldots, a_m$ with $a_i \in A_i$, define $f(A_i) = a_i$. Then $f(A_i) \in A_i$ gives the edge condition, and distinctness of the $a_i$ gives injectivity. So $f$ is a complete matching.
[/guided]
[/step]
[step:Translate Hall's condition and apply Hall's Marriage Theorem]
For any subcollection $\mathcal{B} \subseteq \mathcal{A}$, the neighbourhood of $\mathcal{B}$ in $G$ is
\begin{align*}
\Gamma(\mathcal{B}) = \bigcup_{B \in \mathcal{B}} B.
\end{align*}
Therefore Hall's condition $|\Gamma(\mathcal{B})| \geq |\mathcal{B}|$ for all $\mathcal{B} \subseteq \mathcal{A}$ is exactly the hypothesis $|\bigcup_{B \in \mathcal{B}} B| \geq |\mathcal{B}|$ for every subcollection $\mathcal{B} \subseteq \mathcal{A}$.
By [Hall's Marriage Theorem](/theorems/2018), $G$ has a complete matching from $X$ to $Y$ if and only if Hall's condition holds. By the identification in the previous step, $G$ has a complete matching if and only if $\mathcal{A}$ has an SDR. Combining these two equivalences completes the proof.
[guided]
We now connect the graph-theoretic condition to the set-theoretic one. Take any subcollection $\mathcal{B} \subseteq \mathcal{A}$ and consider it as a subset of $X$. The neighbourhood $\Gamma(\mathcal{B})$ in $G$ consists of all $y \in Y$ adjacent to some $B \in \mathcal{B}$, which means $y \in B$ for some $B \in \mathcal{B}$. So $\Gamma(\mathcal{B}) = \bigcup_{B \in \mathcal{B}} B$.
Hall's condition for the bipartite graph $G$ requires $|\Gamma(\mathcal{B})| \geq |\mathcal{B}|$ for every $\mathcal{B} \subseteq X = \mathcal{A}$. Substituting $\Gamma(\mathcal{B}) = \bigcup_{B \in \mathcal{B}} B$, this becomes $|\bigcup_{B \in \mathcal{B}} B| \geq |\mathcal{B}|$ for every subcollection $\mathcal{B} \subseteq \mathcal{A}$, which is exactly the condition stated in the theorem.
Now we chain the equivalences:
- $\mathcal{A}$ has an SDR $\iff$ $G$ has a complete matching from $X$ to $Y$ (from the previous step).
- $G$ has a complete matching from $X$ to $Y$ $\iff$ Hall's condition holds in $G$ (by [Hall's Marriage Theorem](/theorems/2018)).
- Hall's condition holds in $G$ $\iff$ $|\bigcup_{B \in \mathcal{B}} B| \geq |\mathcal{B}|$ for all $\mathcal{B} \subseteq \mathcal{A}$ (from the translation above).
This gives the desired equivalence.
[/guided]
[/step]
