Prove that a bipartite graph $G$ always has a matching $M$, such that $|M| \gt \frac{|E(G)|}{∆(G)}$.

179 Views Asked by At

How can one prove that a bipartite graph $G$ always has a matching $M$, such that $|M| \gt \frac{|E(G)|}{∆(G)}$, where $E(G)$ is the amount of edges and $∆(G)$ is the maximal degree?