Prove or disprove: A connected undirected Graph G has no Bridge/cut-edge if G is 2k-regular

Question

//Bridge/Cut-edge if after deleting the edge the Graph is not connected anymore.

I think its not true because you could build a Graph G with 2k disconnected-components where in each component exists one node with degree 2k-1. And then you connect all these nodes with degree 2k-1 with a single node in the middle which has degree 2k --> G becomes a connected Graph. And if you delete any of the edges which connect the node in the middle with one of the components you get a disconnected Graph. Hence there exists a bridge.

Can somebody verify my solution or tell me if i made a mistake? And i still need to formalize my solution obviously.

Answer 1

Instead of trying for a counterexample (which would be futile), try instead for a proof.

Hints:

Suppose edge $ab$ is a bridge of $G$, and let $H=G-ab$.

• By definition of bridge, $H$ is not connected.$\\[4pt]$
• Argue that vertices $a,b$ cannot be in the same component of $H$.$\\[4pt]$
• If $A$ is the component of $H$ which contains $a$, argue that all vertices of $A$ other than $a$ have the same degree in $A$ as they had in $G$.$\\[4pt]$
• Now consider the degree of $a$ in $A$.$\\[4pt]$
• So then in $A$, the sum of the degrees has what parity?