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:


*

*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 ?
 A: You have to be allowed to add vertices. In that case it is provable by induction on the number of edges:
Assume G' := G \ e is a Subgraph of some Δ'-regular bipartite Graph K'.
1. Case Δ = Δ' + 1:
K = K' plus e plus an edge for every two other vertices.
2. Case e is in K':
K = K'
3. Case e is not in K':
Let e = (a,b). Because we do not increase Δ, there must be edges in K' \ G' f = (a,c) and g = (b,d).
Make a copy of K' =: K'' and join them. Remove f, g and their copies. Connect e, the copy of e, (a,c'), (b,d'), (a',c), (b',d). Here a' is the copy of a etc.. This gives K with all the right edges and degrees.
We can start the induction at 0 edges, and take as K an edgeless bipartite Graph with partitions of the same size, so that it includes G.
Case 3 can done sometimes without the doubling of the graph, but not always. Your example is a case, which can be solved by doubling the graph. Adding vertices is also no problem for your point 1, because it is independent of the number of vertices.
A: This is ancient history but I thought I'd post a quick alternative fix to the multiple-edge issue, in case this was useful to anyone (I taught this recently and came across this exact problem).
To begin with add vertices of degree $0$ so the graph has the same number of vertices on each side.
Now proceed as in the original proof; only if you were going to add an edge $xy$ there, instead add an entire new $K_{\Delta(G),\Delta(G)}$ with one of its edges $ab$ removed, and then also add edges $xb$ and $ya$.
A: I'm wondering if this is an appropriate solution, I'd love some feedback:
Let $G$ be a bipartite graph with $n>2$ vertices and assume that $X'(G) \lt \Delta(G)$. Recognize that the bipartite graph with $n$ vertices which contains the smallest possible $\Delta(G)$ is a simple path $P:=(v_1,e_1,v_2,e_2,..,e_{n-1},v_n)$ where each partition of the graph contains every other vertex. It is clear that in this case, $\Delta(G)=2$ which is a contradiction because a proper coloring which would correspond to $X'(G)=1$ is impossible in a connected graph with more than 2 vertices. Also, notice that a coloring of 2 is exactly $X'(G) =\Delta(G)=2$ and any coloring which uses more than 2 colors is not minimized.
On the other hand, the bipartite graph with $n$ vertices which contains a vertex which has the highest possible $\Delta(G)$ is the complete bipartite graph $K_{1,n-1}$. Here, the lone vertex in a partition of its own has $\Delta(G)=n-1$. Here we can see that a coloring $X'(G) \lt n-1$ is impossible because there are exactly $n-1$ incident edge. Notice that a coloring of exactly $X'(G) = \Delta(G)=n-1$ is the only proper coloring of $G$ and any color set which has more than $n-1$ elements is nonsensical (more colors than edges).
Therefore any bipartite graph with $n$>2 vertices has a chromatic edge coloring of $X'(G) = \Delta(G)$.  
