draw a graph which is both regular and bipartite.
Answers
Answered by
1
Counterexample shown here for just adding edges:
counterexample: the union of a complete bipartite graph with 4 vertices on either side and a complete bipartite graph with 2 vertices on either side
If k=5k=5, then you'd need another 33 edges from each of the vertices in {5,6}{5,6}. Because 55 and 66 already have edges to 1111 and 1212, all of those additional edges must be to vertices in {7,8,9,10}{7,8,9,10}. But all vertices in {7,8,9,10}{7,8,9,10} already have degree 44, and thus can only accept one edge each. That means that only a total of 44 edges from {5,6}{5,6} can be accepted, leaving 22 stubs on {5,6}{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)G=(X,Y,E),
∑x∈Xd(x)=∑y∈Yd(y)=|E|
∑x∈Xd(x)=∑y∈Yd(y)=|E|
since each edge counts towards the degrees of one vertex in both XX and YY.
We have assumed GG is balanced, so let m≡|X|=|Y|m≡|X|=|Y|. Furthermore, we assume k<mk<m.
Since d(i)≤k,∀i∈X∪Yd(i)≤k,∀i∈X∪Y, |E|≤km|E|≤km.
Case 1: |E|=km|E|=km. Then d(i)=kd(i)=k, so done.
Case 2: |E|<km|E|<km. Then for every vertex ii, put k−d(i)k−d(i) stubs on ii (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 kk. 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|km−|E| stubs to vertices in XX. Order them {s1,...,skm−|E|}{s1,...,skm−|E|}. Similarly, we can order the stubs in YY as {t1,...,tkm−|E|}{t1,...,tkm−|E|}.
Then just join together sjsj and tjtj for j∈[1,km−|E|]j∈[1,km−|E|], and you have your new regular balanced bipartite graph G′G′.
counterexample: the union of a complete bipartite graph with 4 vertices on either side and a complete bipartite graph with 2 vertices on either side
If k=5k=5, then you'd need another 33 edges from each of the vertices in {5,6}{5,6}. Because 55 and 66 already have edges to 1111 and 1212, all of those additional edges must be to vertices in {7,8,9,10}{7,8,9,10}. But all vertices in {7,8,9,10}{7,8,9,10} already have degree 44, and thus can only accept one edge each. That means that only a total of 44 edges from {5,6}{5,6} can be accepted, leaving 22 stubs on {5,6}{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)G=(X,Y,E),
∑x∈Xd(x)=∑y∈Yd(y)=|E|
∑x∈Xd(x)=∑y∈Yd(y)=|E|
since each edge counts towards the degrees of one vertex in both XX and YY.
We have assumed GG is balanced, so let m≡|X|=|Y|m≡|X|=|Y|. Furthermore, we assume k<mk<m.
Since d(i)≤k,∀i∈X∪Yd(i)≤k,∀i∈X∪Y, |E|≤km|E|≤km.
Case 1: |E|=km|E|=km. Then d(i)=kd(i)=k, so done.
Case 2: |E|<km|E|<km. Then for every vertex ii, put k−d(i)k−d(i) stubs on ii (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 kk. 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|km−|E| stubs to vertices in XX. Order them {s1,...,skm−|E|}{s1,...,skm−|E|}. Similarly, we can order the stubs in YY as {t1,...,tkm−|E|}{t1,...,tkm−|E|}.
Then just join together sjsj and tjtj for j∈[1,km−|E|]j∈[1,km−|E|], and you have your new regular balanced bipartite graph G′G′.
Similar questions