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

//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.

• In your proposed construction, the components have exactly one vertex of odd degree, but that's not possible, since the sum of the degrees must be even. Jul 14, 2021 at 10:17
• The vertex with odd degree should get a even degree when theyre connected to my "middle" vertex. But i failed to draw this and might need to think of sth else. Jul 14, 2021 at 11:17
• But before the connection, the component has exactly one vertex of odd degree, which is not possible. Jul 14, 2021 at 11:47

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?
• a in A has an uneven degree since 2k-1=always uneven. Hence in A the sum of degrees has an uneven parity. The same goes for the other component i suppose and in total there is an even degree again. --> No matter how many edges are deleted i will always have a connected graph? Because for every deleted edge there is another one because of 2k ? Jul 14, 2021 at 15:47
• i got it: in every Graph G the number of vertices with uneven degree is even which is a contradiction Jul 14, 2021 at 20:50