In: Advanced Math
Let G be a bipartite graph and r ∈ Z>0. Prove that if G is r-regular, then G has a perfect matching.
HINT: Use the Marriage Theorem and the Pigeonhole Principle. Recall that G is r-regular means every vertex of G has degree
To prove this result we will required two results:
Result 1:
Hall's Theorem:
Let G be a bipartite graph with bipartition . Then G contains a matching that saturates every vertex in if and only if .
Result 2:
If is a K-regular bipartite graph with K > 0 then where and are bipartition of .
Suppose is a K-regular bipartite graph with bipartition and
......................By Result 2
Let then
Suppose and are the sets of edges incident with vertices in and respectively.
Clearly by definition of ,
and Hence by Hall's theorem has a matching M saturating every vertex in .
M is perfect matching
has a perfect Matching.