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:
- Proving the theorem for regular bipartite graphs;
- 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 ?