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$?
bipartite simple graph matching-proof
0
$\begingroup$
graph-theory
-
0It's not clear in your statement of the problem whether or not every vertex is to still have the same degree. – 2012-07-07
-
0The 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
-
0No. Does every vertex have the same degree or may vertices have different degrees? – 2012-07-07
-
0The 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