Families of Sets, associate Bipartite Graph For each of the following families of sets, construct the associated bipartite graph.
If possible, find a system of distinct representatives. If there is no such system,
explain why.


*

*A1 = {1, 2, 3}, A2 = {2, 3, 4}, A3 = {1}.

*A1 = {1, 2, 3, 4, 5}, A2 = {1, 3}, A3 = {1, 3}, A4 = {1, 2, 3, 4, 5}, A5 = {1, 3}
I have tried this problem a few times, but still do not understand it. Can someone please show me how this problem is solved
 A: I’ll do the first one as an example and leave the second to you. Let $G$ be the associated bipartite graph. One of the two sets of vertices of $G$ is the collection $U=\{A_1,A_2,A_3\}$ of sets in the family. The other is $V=A_1\cup A_2\cup A_3$, the set of all members of any of those sets. An element $k\in V$ is connected by an edge of $G$ to a set $A_\ell\in U$ if and only if $k\in A_\ell$. Thus, the vertex $1$ is connected by edges to vertices $A_1$ and $A_3$, vertex $2$ is connected by edges to vertices $A_1$ and $A_2$, vertex $3$ is also connected by edges to vertices $A_1$ and $A_2$, and vertex $4$ is connected by an edge to vertex $A_2$.
A system of distinct representatives for $U$ corresponds to a matching of $G$ that saturates $U$, i.e., a set $M$ of edges of $G$ such that no two members of $M$ have a vertex in common, and every vertex in $U$ is a vertex of some edge in $M$. For each $S\subseteq U$ let $N(S)$ be the set of all vertices in $V$ connected to be an edge of $G$ to some vertex in $U$. (You should check that $N(S)=\bigcup_{A_\ell\in S}A_\ell$.) Hall’s theorem says that there is such a matching if and only if $|S|\le|N(S)|$ for each $S\subseteq U$. If you check the $2^3=8$ subsets of $U$, you’ll find that this is the case for each of them. For instance, for $S=\{A_1,A_3\}$ we have $N(S)=A_1\cup A_3=\{1,2,3\}$, and $|S|=2\le 3=|N(S)|$. Thus, by Hall’s theorem the family $U$ must have a system of distinct representatives. 
It’s not hard to find one by inspection. Clearly we must match $A_3$ with $1$, its only element. We can then match $A_1$ with either $2$ or $3$. If we match $A_1$ with $2$, we can match $A_2$ with $3$ or $4$, and if we match $A_1$ with $3$, we can match $A_2$ with $2$ or $4$, so we actually have a choice of four different systems of distinct representatives in this case.
