# Showing a bipartite graph has a perfect matching.

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$.

## 1 Answer

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$.