# Perfect Matching in Graph Theory.

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!

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

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.