Let G be a K-regular bipartite graph with k ≥ 2. Then G has no cut edge

Question

how is this statement correct..can some one give an example??

Let G be a K-regular bipartite graph with k ≥ 2. Then G has no cut edge

Answer 1

K - regular bipartite graph means we will have bipartite graph of the form K_2,2 , K_3,3 etc..

In general in K_k,k the degree of each vertex will be k and it will be a bipartite graph..

Now coming to the cut edge , it means that removal of such edge will disconnect the entire edge..

But we do not get any such edge in K - regular bipartite graph , provided K >= 2 , because after removal of that edge , then the degree of the vertex on which it was incident will decrease by 1 only ..But being K >= 2 , the minimum degree that the vertex may have is 1 after removal of an edge from this graph..Thus ensuring the connectivity of the graph.

.Had K >= 1 then there would have been a possibility of degree of that particular vertex = 0 and in that case that vertex would be isolated from the remaining graph and in other words the original graph would get disconnected..

I hope this reasoning helps you..

Thus no edge will not disconnect the K regular bipartite graph on its removal.So no existence of cut edge for such graph..

Comments

@habibkhan,i think this can be the exampl for k regular bipartite to be not cocmplete bipartite

here n=m but it is not complete bipartite.

---

@Akriti. Yes, right.

---

for Knn bipartite graph removal of  n edges would make a vertex isolated