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
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.