extending bipartite Graphs to regular bipartite Graphs

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.

• Suppose each partition has $2$ vertices, and $k=10000$, you still skip the step? Also, even if you have sufficient vertices, it is not obvious whether your approach of just pairing up insufficient vertices will work. You should try proving it. Currently it is just an idea (i.e. not a proof), which might/might not work. – Aryabhata Feb 15 '12 at 1:30
• right, if k > max{|X|,|Y|} then it s trivial though, as I will just add vertices to each until they have cardinality k and then I can embed G in G' = K(k,k) (i.e. in the complete Bipartite Graph with degree k for each vertex ) I ll ammend my question accordingly, tks! – Beltrame Feb 15 '12 at 1:49
• @Aryabhata: I totally see what you are saying, because that s exactly my problem; namely I fail to see how my pairing argument is not trivial, even though I feel a little uneasy about it. I m not sure how to make it more evident though (in case it actually works) – Beltrame Feb 15 '12 at 2:00

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.

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

• How do you avoid joining multiple stubs between the same two vertices? – Aryabhata Feb 15 '12 at 7:19
• The problem states, "$k$ exceeds the degree of each vertex," so you can't use $k=2$ in your "counterexample". 2 doesn't exceed 2. – Gerry Myerson Feb 15 '12 at 12:16
• I think the way you've been updating your answer in response to comments has been exemplary. Separate answers are only useful if you have two quite different solutions to the same problem and want to present them separately. – joriki Feb 15 '12 at 15:30
• @PeeJay: Yep, that's why I mentioned that my solution is incorrect. I'll edit it to make it more obvious that the solution is wrong. Will think more about the other solution you outlined when I have a bit more time tonight/tomorrow. – Yun William Yu Feb 15 '12 at 21:55
• @PeeJay: Don't have the reputation yet to comment on your post so I'll do it here. I don't think that quite works, because you don't guarantee that the last copy of X- has available stubs outside of the last copy of Y-. That is to say, what if, when you get to the last X-, you've used up almost all the capacity of the first delta-1 copies of Y-. In that case, the first delta-1 copies of Y- aren't completely used up yet, so you can't just delete the last G'. However, there isn't enough capacity in the first delta-1 copies of Y- to hold the last X-, and you're forced into the last Y-, so error. – Yun William Yu Feb 15 '12 at 23:38

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
• $$G\subset 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 $$E\cup 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_i\tilde{u}_i \,:\, \deg(u_i)< \Delta\},$$ $$E_3 := \{ v_j\tilde{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$$.