1
$\begingroup$

Problem: Let $k$ be a positive integer, and let $G$ be a bipartite graph in which every vertex has degree $k.$ Prove that the edges of $G$ can be partitioned into $k$ perfect matchings.

My Attempt: By simple application of Hall's Theorem, I have shown that $G$ has a perfect matching. However, I am not sure that I understand the language of the problem, i.e. what do we have to prove? What do you mean by the sentence that " the edges can be partitioned into $k$ perfect matchings". This does not make sense to me and I am unable to trace a related definition in my textbook. Please help!

$\endgroup$
  • 1
    $\begingroup$ It means that you can colour the edges in $k$ colours so that from each vertex exactly one edge of each colour emerges. $\endgroup$ – Lord Shark the Unknown Apr 26 '17 at 20:10
  • $\begingroup$ Makes sense. Thank you! $\endgroup$ – model_checker Apr 26 '17 at 20:13
2
$\begingroup$

You have proved the following: A $k$- regular bipartite graph has a perfect matching.

This immediately proves that every $k$-regular graph can be partitioned into perfect matchings by using induction on $k$, because after you remove a perfect matching you get a $k-1$-regular bipartite graph.

$\endgroup$
2
$\begingroup$

See the definition of Perfect Matching here. Simple induction is all that is needed.

$\endgroup$

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.