Statement:
Let G[X, Y ] be a bipartite graph without isolated vertices such that $$ d(x) ≥ d(y)\:\: \forall xy\in E, where \: x\in X \: and\: y\in Y. $$ Then $$ |X|\leq|Y| $$ with equality if and only if d(x) = d(y) $$\forall xy\in E.$$ Proof: The first assertion follows if we can find a matrix with |X| rows and |Y | columns in which each row sum is one and each column sum is at most one.
Such a matrix can be obtained from the bipartite adjacency matrix B of G[X, Y ] by dividing the row corresponding to vertex x by d(x), for each x ∈ X. (This is possible since d(x) = 0.)
Because the sum of the entries of B in the row corresponding to x is d(x), all row sums of the resulting matrix B' are equal to one.
On the other hand, the sum of the entries in the column of B' corresponding to vertex y is $$ \Sigma 1/d(x) $$ the sum being taken over all edges xy incident to y.
This sum is at most one because 1/d(x) ≤ 1/d(y) for each edge xy, by hypothesis, and because there are d(y) edges incident to y.
The above argument may be expressed more concisely as follows. $$ |X|=\sum_{x\in X}\:\sum_{y\in Y \: xy\in E} \frac {1}{d(x)} =\sum_{x\in X \:y\in Y}\:\sum_{xy\in E}\frac{1}{d(x)} \leq \sum_{x\in X \:y\in Y} \: \sum_{xy \in E} \frac{1}{d(y)} =\sum_{y\in Y}\:\sum_{x \in X \: xy \in E} \frac{1}{d(y)}=|Y| $$
Furthermore, if $$|X|=|Y|$$ the middle inequality must be an equality, implying that $$ d(x)=d(y) \:\: \forall xy\in E. $$
I don't understand
- how the first assertion follows from finding "a matrix" in which each row sum is one and each column sum is at most one.
- what is the matrix B'
- the equation with lot of sigmas
If on every edge $xy$ of the graph you write the number $\frac{1}{d(y)}-\frac{1}{d(x)}$, then the sum of all these numbers equals $|Y|-|X|$. On the other hand the sum is nonnegative (by your assumption) and if $d(x)>d(y)$ (strictly) for at least one edge, then the sum is strictly positive. That's all.