Let $G = (V, E)$ be a bipartite graph with $n$ nodes on each side. Show that if the degree of each vertex is greater than $n/2$, then $G$ has a perfect matching.

My thoughts are to use the Marriage Theorem which my book states as

A bipartite graph has a perfect matching if and only if $|A| = |B|$ and for any subset of (say) $k$ nodes of $A$ there are at least $k$ nodes of $B$ that are connected to at least one of them.

It is easy to show that any subset of $A$ of fewer than $n/2$ nodes is connected to at least $n/2$ nodes in $B$. However, I do not know how to conclude anything about bigger subsets of $A$.


Suppose $X\subseteq A$ and $|X|\gt n/2$. Then every vertex in $B$ must be adjacent to a vertex in $X$, because any vertex in $B$ which is adjacent to no vertex in $X$ would have degree $\le|A|-|X|=n-|X|\lt n-n/2=n/2$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.