# Edge-coloring of bipartite graphs

A theorem of König says that

Any bipartite graph $G$ has an edge-coloring with $\Delta(G)$ (maximal degree) colors.

This document proves it on page 4 by:

1. Proving the theorem for regular bipartite graphs;
2. Claiming that if $G$ bipartite, but not $\Delta(G)$-regular, we can add edges to get a $\Delta(G)$-regular bipartite graph.

However, there seem to be two problems with the second point:

• A regular bipartite graph has the same number of vertices in the two partions. So we need to add vertices also.
• I'm not sure that it is always possible to add edges to get a $\Delta$-regular bipartite graph, even if we have the same number of vertices. See the figure below. B and E both have degree two, but we cannot make them degree 3

Am I right ? Is there a way to correct that ?

-
A good way to do this is to prove that any bipartite graph has a matching that covers each vertex of maximum degree. (The proof of this is got using the ideas you'd use to prove Koenig's theorem. It's not trivial.) As your example shows, you cannot always make a bipartite graph regular by adding edges. –  Chris Godsil Jul 2 '12 at 14:04
Is there is any problem with having multiple edges in this proof? If not you can just add another edge between E and B. Similarly, it is possible to add isolated vertices to the graph (to get the same number of vertices in each set) before adding the edges and the colouring of the regular graph thus formed will transfer back to the original graph. –  jp26 Jul 2 '12 at 14:07