Prove the following :
If $G$ is a regular bipartite graph, then $G$ has a perfect matching.
If $G$ is $k$-regular bipartite graph then it has an edge coloring using exactly $k$ colors.
If $G$ is a bipartite graph with maximum degree $\Delta$ then it has an edge coloring using exactly $\Delta$ colors.
Posted: Jul 11 '12
Seen: 79 times
Last updated: Aug 12 '12