graph theory
A bipartite graph with partite sets U and W is called balanced if |U| = |W|.
Let G be a regular bipartite graph with at least one edge. Prove that G is balanced.
A regular graph means that every vertex has the same degree this implys that (using the bipartite property) the number of vertices in U = W again by it being bi partite and having vertices of equal degree implys that |U| = |W|.
At least in my head that makes sense any hint how to prove it?
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.
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'$.
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.
Best Answer
Let the degree of every node be $d$ (and since the graph has at least one edge, $d>0$). Then the number of edges associated with nodes in $U$ is $|U|d$, and the number of edges associated with nodes in $W$ is $|W|d$. Every edge in the bipartite graph connects a node in $U$ with a node in $W$, thus the total number of edges associated with the two parts is the same.
Thus $|U|d = |W|d$ and $|U| = |W|$