Marriage theorem: If G is K- regular bipartite graph with k>0, then G has a perfect matching.

 If G is K- regular bipartite graph with k>0, then G has a perfect matching.

Let G be k- regular bipartite graph. counting the end points inX and by endpoints in Y shows that \[K\left | X \right |=K\left | Y \right |\]so\[\left | X \right |=\left | Y \right |\]

Hence it sufficies to verify Hall's condition; a matching that saturates X will also saturate Y and be a perfect matching.

Consider\[\left | X \right |=\left | Y \right |\]. Let m be the number of edges from S to N(S).

Since G is k- regular, \[m=k\left | S \right |\]

These m edges are incident to N(S), so \[m\leqslant k\left | N(S) \right |\]

Hence