1
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – quasi
    Jul 14, 2021 at 10:17
  • $\begingroup$ 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. $\endgroup$
    – Student 1
    Jul 14, 2021 at 11:17
  • $\begingroup$ But before the connection, the component has exactly one vertex of odd degree, which is not possible. $\endgroup$
    – quasi
    Jul 14, 2021 at 11:47

1 Answer 1

1
$\begingroup$

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?
$\endgroup$
2
  • $\begingroup$ 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 ? $\endgroup$
    – Student 1
    Jul 14, 2021 at 15:47
  • $\begingroup$ i got it: in every Graph G the number of vertices with uneven degree is even which is a contradiction $\endgroup$
    – Student 1
    Jul 14, 2021 at 20:50

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .