I am working on this problem trying to show for a bipartite graph $G$ when given $k in mathbb{N}$ such that $k$ exceeds the degree of each vertex $v in V(G)$ I can construct a new graph $G'$ simply by adding vertices and edges in such a way that I end up with a bipartite graph $G'$ in which each vertex has degree $d(v) = k$.

I am wondering whether it should not be possible simply to extend the smaller part of the bipartition with vertices such that both parts end up having the same number of vertices.
(the step is superflous if the bipartitions already have the same cardinality in G, and without loss of generality I assume k < max{|X|,|Y|} because otherwise I ll just add vertices to each so they have cardinality k and I can embed G in the complete bipartite graph with degree k of each vertex)

Now since I want each vertex $v$ to have degree $k$ and since both parts of the bipartition now end up having the same number of vertices it would seem they have the same "capacity" for incoming edges from the other part of the partition respectively.

Does this not mean that I will certainly be able to now add edges as needed to ensure each vertex has degree $k$ ? (i.e. I keep all the "old" edges from G and just add edges essentially pairing vertices in G' that still have insufficient degree)

It would seem this way I can ensure I embed G into a bipartite G' such that G' is regular. (i.e. regular in the sense that it has vertices each of degree k)

I think I m missing something...

ctd....

OK, I think I see why my strategy will not generally work. Basically to keep it short we cannot be sure that the we can actually match up the "capacity" that I was talking of above. (tks and credit also at this point to the counterexample provided below !)

I have a proposal how to fix the situation though:

match capacity in G' as described above until you cannot continue. You will be left with a subset of vertices in X' and Y' call them $X^-$ and $Y^-$ that do not have the required degree yet. The sum over the deficient degrees will be equal though, as outlined before. Call this sum $Delta X = Delta Y = Delta $. (The only problem is we are not able to match them up anymore within G')

Now add further vertices and edges so as to add $Delta$ "carbon" copies of G'. You can now go through the vertices in $X^-$ and for each incoming edge that is missing you add 1 edge going to one of the copies.

So doing this you get an edge from $X^-$ to each copy of $Y^-$. This cannot run into trouble, because you have capacity, and at the time when you add the edge the parts of the Graph are disconnected. Now $X^-$ is fixed.

In a similar way you proceed for each copy of $X^-$ and at each step you ignore the respective copy of $Y^-$ that is in the same copy of G'. Since the sum over the whole spare capacity of the respective parts of the bipartition of the new extended Graph are again the same, and since you never try to add an edge between parts of the enlarged Graph that are already connected, this strategy should work.

Counterexample shown here for just adding edges:

If $k=5$, then you'd need another $3$ edges from each of the vertices in ${5,6}$. Because $5$ and $6$ already have edges to $11$ and $12$, all of those additional edges must be to vertices in ${7,8,9,10}$. But all vertices in ${7,8,9,10}$ already have degree $4$, and thus can only accept one edge each. That means that only a total of $4$ edges from ${5,6}$ can be accepted, leaving $2$ stubs on ${5,6}$ with no place to go.

It might still be possible to extend the graph if you add both edges and vertices, but I'm not sure how to systematically do that.

Incorrect old answer:

My original answer was incorrect as highlighted by Aryabhata's comment (unless you allow for weighted graphs or multigraphs), but I've left it below for reference.

Succinctly, yes. You've basically already answered the question.

I'll try to flesh it out a bit to make it more evident, but really I'm just repeating your own intuition:

Given a bipartite graph $G=(X,Y,E)$, $$ sum_{x in X} d(x) = sum_{y in Y} d(y) = |E| $$
since each edge counts towards the degrees of one vertex in both $X$ and $Y$.

We have assumed $G$ is balanced, so let $m equiv |X| = |Y|$. Furthermore, we assume $k < m$.

Since $d(i) le k, forall i in X cup Y$, $|E| le km$.

Case 1: $|E| = km$. Then $d(i) = k$, so done.

Case 2: $|E| < km$. Then for every vertex $i$, put $k - d(i)$ stubs on $i$ (recall that a stub is half of an edge, two stubs on different vertices can be joined to form an edge between those vertices, and that a stub counts towards the degree of a vertex).

Now, all vertices have degree $k$. However, we still need to join the stubs together to form edges to turn this back into a bipartite graph. Note that we added a total of $km - |E|$ stubs to vertices in $X$. Order them ${s_1, ..., s_{km-|E|}}$. Similarly, we can order the stubs in $Y$ as ${t_1, ..., t_{km-|E|}}$.

Then just join together $s_j$ and $t_j$ for $j in [1,km-|E|]$, and you have your new regular balanced bipartite graph $G'$.

Let $G(L,R,E)$ be a bipartite graph, with maximal degree $Delta(G) = Delta$, and minimal degree $delta(G) = delta$. We assume $delta < Delta$, for otherwise $G$ is $Delta$-regular and we're done.

Let $L={v_1,ldots,v_n}$, and $R={u_1,ldots,u_m}$.

We'll construct a bipartite graph $G'$, such that:

• 
  $Delta(G') = Delta$,


• 
  $delta(G')=delta+1$, and


• 
  $Gsubset G'$.

Since the minimal degree strictly increases, applying this construction precisely $Delta-delta$ times, gives us an embedding of $G$ in a bipartite $Delta$-regular graph, as desired.

Here's the construction:

Define the graph $G'(L',R',E')$ as follows:

• 
  $L' := L cup {tilde{u}_1,ldots,tilde{u}_m }$,


• 
  $R' := R cup {tilde{v}_1,ldots,tilde{v}_n }$,

so to $L$ we add a copy of $R$ to form $L'$, and similarly to $R$ we add a copy of $L$ to form $R'$.

Since $G$ is bipartite, all the edges in $E$ are of the form $u_iv_j$. To define $E'$, we first duplicate the edges of $E$ to the tilde vertices:
$$ E_1 := { tilde{u}_i tilde{v}_j ,:, u_iv_j in E }. $$
Note that with these edges (i.e. with $Ecup E_1$),
$$ deg (u_i) = deg (tilde{u}_i), $$
$$ deg (v_j) = deg (tilde{v}_j), $$
for all $i=1,ldots,m$ and $j=1,ldots,n$.

We define two more sets of edges:
$$ E_2 := { u_itilde{u}_i ,:, deg(u_i)< Delta},$$
$$ E_3 := { v_jtilde{v}_j ,:, deg(v_j)< Delta},$$
and finally,
$$ E' = E cup E_1 cup E_2 cup E_3.$$
This ends the construction. $G'$ is clearly bipartite, and it contains $G$ as a subgraph. Also, it has $Delta(G')=Delta$, and $delta(G')=delta+1$.