0
$\begingroup$

Prove that if $G$ is a bipartite simple graph and every vertex has the same degree $k$, then the edges of $G$ can be partitioned into $k$ matchings. Can we then prove the same if every vertex has degree $\le k$?

  • 0
    It's not clear in your statement of the problem whether or not every vertex is to still have the same degree.2012-07-07
  • 0
    The second bit asks whether the same can be proven if every vertex has degree AT MOST $k$ rather than $=k$. Does that answer your question?2012-07-07
  • 0
    No. Does every vertex have the same degree or may vertices have different degrees?2012-07-07
  • 0
    The first proof requires that all vertices have deg=k, while the second doesn't(but has a max cap on deg=k).2012-07-07
  • 1
    @TimDuff Note that the question does not require the $k$ matchings to be perfect.2012-07-07

3 Answers 3