Colouring bipartite graph with sets of possible colors to each vertex I'm having some trouble with proving the following: Let $|S(v)|$ be the set of colours available to colour vertex v. The claim is that for every bipartite graph $G=(V,E)$, if $|S(v)| > log_2n$ for each v then it is possible to find a valid colouring of G.
Any hints?
Thanks.
 A: Disclaimer:
This is a simplified proof from Nancy Eaton's On Two Short Proofs About
List Coloring Graphs
. It's rather simple, but I was unable to form hints in a way that would make the intention clear, so I present all the details. As this is homework, please make an additional effort to rework the proof again, only by yourself.
Also, should you need to hand it in, be sure to cite Nancy Eaton's paper as a reference.

Let $C$ be the set of all the colors, i.e. $C = \bigcup_{v \in V} S(v)$, and set $V_0, V_1$ to be the bipartition of the graph.
We will prove that there exists a function $f : C \to \{0,1\}$ such that 
$f^{-1}(0)$ and $f^{-1}(1)$ indicate proper colorings for the $V_0$ and $V_1$ parts of the bipartite graph respectively. To prove our claim it is enough to show that for all $v \in V_i$ we have
$$S(v) \cap f^{-1}(i) \neq \varnothing$$
The proof will be probabilistic, that is, consider a random function $f : C \to \{0,1\}$, i.e. one picked uniformly from ${\{0,1\}}^C$. We have that for any $c \in C$
$$\mathbb{P}\Big(f(c) = 0\Big) = \frac{1}{2}.$$
Now
\begin{align}
\mathbb{P}\Big(\exists v \in V_i.\ S(v) \cap f^{-1}(i) = \varnothing\Big) 
&\leq \sum_{v \in V_i} \mathbb{P}\Big(S(v) \cap f^{-1}(i) = \varnothing\Big) \\
&\leq \sum_{v \in V_i} \left(\frac{1}{2}\right)^{|S(v)|} \\
& < \sum_{v \in V_i} \frac{1}{n}
\end{align}
Summing it up for both $i = 0$ and $i = 1$ we get
$$\mathbb{P}(f \text{ fails for some } v \in V) < \sum_{v \in V} \frac{1}{n} = 1.$$
That means, that there is a non-zero probability that it won't fail, and as we are in discrete, finite probability space, there exists $f$ that satisfies all the constraints.
I hope this helps $\ddot\smile$
