Edge-coloring of bipartite graphs

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.

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$.