Hall’s Theorem states that for sets $ A_1,…,A_n$ if and only for all $ J\subseteq \{1,…,n\}$ we find $ |\bigcup_{j\in J}A_j|\geq|J|,$ then we can choose $ x_i\in A_i$ for all $ i$ such that $ \{x_1,…,x_n\}$ is a system of distinct representatives for $ A_1,…,A_n.$ To me it seems easiest to some inductive argument (or a contradiction that is similar to induction), however, in my graph theory class we’re working with Flow Algorithm’s, so the goal is to solve it using the Max-Flow-Min-Cut Theorem. I’ve seen one proof using that theorem, but I think I’ve came up with another, which to me seems more natural. I was wondering if my proof is correct. Here’s the proof.

$ \textbf{Proof:}$

Throughout $ x$ shall refer to an element of some $ A_i.$ We set up a capicated network as follows $ $ \overrightarrow{E}=\{(s,A_i):\forall A_i\}\cup\{(A_i,x):\forall A_i\text{ and }x\in A_i\}\cup\{(x,t):\forall x\in \cup_{i=1}^n A_i\}$ $ with capacities for $ (s,A_i)$ and $ (x,t)$ all $ 1$ and all other capacities infinite. This is ‘depicted’ in the following link, where any unwritten capacity is infinite.

Now we suppose that we have a minimal network cut $ U.$ So the sum of capacities of edges leaving $ U$ is minimal. If $ A_i\in U,$ and $ x\not\in U$ for sum $ x\in A_i,$ then $ (A_i,x)$ is an edge leaving $ U$ with infinite capacity, and $ \{s\}$ has smaller capacity than $ U,$ impossible. So $ x\in U$ for all $ x\in A_i$ . We compute $ $ \text{capacity}(U)=\sum_{A_i\not\in U}\text{capacity}(s,A_i)+\sum_{x\in U}\text{capacity}(x,t)=|\{A_i\}\backslash U|+|\{x:x\in U\}|$ $ $ $ \text{capacity}(U)\geq|\{A_i\}\backslash U|+|\{x\in A_i: A_i\in U\}|\geq|\{A_i\}\backslash U|+|\{A_i\in U\}|=n.$ $ Thus since $ \text{capacity}\{s\}=n$ we find that $ \{s\}$ is a min cut, and we can find a system of distinct representatives. $ \blacksquare$