bipartite graph and size of partitions Given a finite graph $G$ which is bipartite with partitions $A$ and $B$ and has no vertices without edges.
For any neighbouring $x \in X$ and $y\in Y$ it holds that $\operatorname{deg} x \geq \operatorname{deg} y$.
How to show, that $|X| \leq |Y|$? (equality, when $\operatorname{deg} x = \operatorname{deg} y$ for all neighbouring $x \in X$ and $y\in Y$).
It certaily holds, that $\sum_x \operatorname{deg} x = \sum_y \operatorname{deg} y$. But I lack a idea to formally derive the statement about the cardinalities of $X$ and $Y$.
 A: (I expect this statement must have a shorter and more elegant proof, but I was unable to come up with one.)
We use induction on the maximum degree $k$ of the graph.
Induction base: $k=1$.
Since there are no isolated vertices every vertex has degree exactly 1, so the edges
form a perfect matching and $|X|=|Y|$.
Induction step: We assume $k>1$ and the statement proven for all
graphs with smaller maximum degree. Now assume that $G$ is the smallest graph with
maximum degree $k$ for which the statement is false.
Let $P$ be the subset of $X$ containing the vertices of degree $k$
and $Q$ the subset of $Y$ containing the vertices of degree $k$.
$P$ cannot be empty or $Q$ would have to be empty as well and we do not have maximum degree $k$.
If $Q$ would be empty, then we can remove one edge from some vertex in $P$.
This leads to a smaller graph $G'$ with bipartition $X,Y'$, where $Y'$ is either equal to $Y$
or has one element less.
The degree requirement is still satisfied in $G'$, so $|X|\leq|Y'|\leq|Y|$. Contradiction.
So $Q$ is not empty either.
Each vertex of $Q$ has $k$ edges and they all must go to vertices of $P$.
Furthermore each vertex of $P$ can only accomodate only $k$ edges.
This means that the marriage condition (or "Hall's condition") for $Q$ is fulfilled
in the $P,Q$-subgraph, so there is a matching of $Q$.
Now remove the edges of this matching and again you find a smaller graph still satisfying the degree condition
proving that $|X|\leq|Y|$ after all. This final contradiction proves the statement.
