How can I prove that this two statements are equivalent?

Question

Given: complete graph G and I a list assignment for G
prove: G has proper coloring $\Leftrightarrow $ $ \forall \;Z\subseteq V(G)$ : $\mid Z \mid \leq \mid \cup_{z\in Z}\; I(z) \mid $

Can someone give me a hint how to solve it?

Answer 1

Consider an auxiliary bipartite graph $H$ defined as follows. One of partite set of $H$ is the set $V=V(G)$ of vertices of $G$ and the other is the set $C=\cup_{z\in V} I(z)$ of all given colors. An edge between a vertex $z\in V$ and a color $c$ exists, if $c\in I(z)$. A matching $\mathcal M$ on $H$ is called $V$-saturating provided each vertex of $V$ belongs to an edge from $\mathcal M$. There exists a natural bijection $f=\{(v,c(v)):v\in V\}$ between proper colorings $c$ of $G$ and $V$-saturating matchings on $H$. So $G$ has a proper coloring iff there exists a $V$-saturating matching on $H$. By Hall marriage theorem this holds iff $$ \forall \;Z\subseteq V : |Z|=|N_H(Z)|= \left| \bigcup_{z\in Z}\; I(z) \right|.$$