 Solution

Let $i(G)$ be the number of independent sets of the biregular graph $G$. Choose one such set $I$ uniformly and write $X_v=1_{v\in I}$. All information entropies below use logarithms to base two, soWe will prove $\boxed{i(G)\le (2^r+2^s-1{)}^{m/s}}$.

We state and justify the entropy facts used. For a finite-valued random variable $Y$, $H(Y)=-{\sum }_y{p}_y{\log }_2{p}_y$ with $0{\log }_{2}0=0$. Its conditional entropy is the mean of this quantity over the conditioning variable. Factoring the joint probabilities proves the chain rule for information entropy, $H(Y,Z)=H(Y)+H(Z\mid Y)$. Conditioning reduces entropy: $H(Y\mid Z,T)\le H(Y\mid Z)$. To see this, condition on $Z$ and use concavity of $-x{\log }_{2}x$ to compare the mixture of the conditional distributions given $T$ with their mean entropy.

The precise Shearer inequality needed here is: if subsets $S_j$ of the indices of a finite random vector $Y$ cover every index at least $d$ times, then $dH(Y)\le {\sum }_{j}H(Y_{S_j})$. To prove it, order the indices. The chain rule for information entropy expandsThe inequality is conditioning reduces entropy. Summing over $j$ counts each nonnegative conditional term at least $d$ times and proves the assertion.

For every $w\in W$, its vertex neighbourhood $N(w)\subseteq U$ has $s$ vertices. Every $u\in U$ lies in exactly $r$ of these neighbourhoods. Hence Shearer inequality givesLet $q_w=\mathbb{P}(X_{N(w)}=0)$, the probability that no neighbour of $w$ is selected. Conditional on a particular selected subset of $U$, a vertex $w$ with a selected neighbour is forbidden, and all other vertices of $W$ are available. Because there are no edges within $W$, every subset of the available vertices is a valid completion. Uniform choice of $I$ makes these completions equally likely. The available coordinates are therefore independent fair binary choices, each of entropy one, and the forbidden coordinates are zero. Averaging their number givesBy the chain rule for information entropy,It remains to bound each bracket. Let $Y=X_{N(w)}$, a binary vector of length $s$, with distribution $(p_y)$ on $\{0,1{\}}^s$, and put $Z=2^r+2^s-1$. Assign weight $w_0=2^r$ to the all-zero vector and weight $w_y=1$ to every nonzero vector. ThenThe first inequality is Jensen's inequality for the concave logarithm; the weights sum to $2^r+(2^s-1)$. This explicitly handles zero probabilities and does not assume the neighbourhood indicators are independent.

There are $n$ right vertices, so combining the bounds and using $rm=sn$ givesExponentiating proves the required independent-set bound for biregular graphs. The proof uses both degree constraints: $r$ supplies the neighbourhood-cover multiplicity and the conditional-completion weight, while $s$ determines the number of neighbourhood patterns.