Past exam question: probabilistic method Let $G=(V,E)$. We want to give for each vertex $v$ in $V$ a number $f_v$ s.t. for every vertex we have
$$ (\sum_{v: (u,v)\in E} f_v)+f_u \not \equiv 0 \mod{(n+1)}$$ 
Let A be the following algorithm to solve the problem:
For each vertex, select a random number between $0$ and $n$ see if it is a good solution. If so, return the solution, otherwise - return to the beginning of the algorithm.


*

*Prove that if there is a solution, the running time of the algorithm is polynomial. What's the expectation?

*Use the probabilistic method to prove that there is always a solution to the problem.

 A: HINT: The function 
$$g(v) \doteq f_v + \sum_{u: uv \in e(G)} f_u  \mod (n+1) $$
is uniformly distributed amongst $\{0,1,\ldots, n \}$ so for any graph $G$ on $n$ vertices the following holds: For each vertex $v \in G$, the probability that $g(v)$ is 0 is $\frac{1}{n+1}$. Thus by the union bound the probability that this algorithm fails to find a good solution (for any graph $G$) is at most $n \times \frac{1}{n+1} = \frac{n}{n+1} = 1 -\frac{1}{n+1} >0$. So for any $G$, there is indeed a positive probability that this algorithm will find a solution, which of course implies that there indeed is a solution to be found in the first place.
Furthermore, from the above paragraph the probability that this algorithm fails to find a good solution after $\ell$ iterations is at most $\left(\frac{n}{n+1} \right)^{\ell}$. Thus the expected running time of this algorithm is at most $\sum_{\ell=1}^{\infty} \ell \left(\frac{n}{n+1} \right)^{\ell}$. I leave it to you to show that this is polynomial in $n$.

Now if $g(v)$ were (say) $\sum_{uv \in E(G)} (f_u + f_v)$ then it would not necessarily hold that $g(v)$ is uniformly distributed amongst $\{0,1,\ldots, n\}$. If e.g., $G$ were a multigraph and each edge appeared twice and $n+1$ were even then $g(v)$ would be even as well. [If $n+1$ is even then the parity of $m$ $\mod (n+1)$ is well-defined for all integers $m$]
