I am reading the paper "chain independence and common information" (http://ttic.uchicago.edu/~yury/papers/independ.pdf). In this paper, an inequality is used several times (without proof) which looks interesting to me. I would appreciate if anybody can help me prove it. The inequality is as follows: For random variables X, Y, Z we have $$H(Z)\leq H(Z|X) + H(Z|Y) + I(X;Y)$$ where $H(\cdot)$ is the entropy and $I(\cdot;\cdot)$ is mutual information.

As far as I see in the paper, there is no restriction on the structure of random variables $X,Y$ and $Z$, so they are arbitrary. (Look at the first page or second page of the paper in the proof of Theorem I)