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.