18.4 Variant = Check if graph remains connected if any one edge is removed

#1

Hello. The last variant of problem 18.4 asks to write a program to check if the given undirected graph remains connected if any one edge is removed. We can assume that the given graph is connected.

My theory is that the graph will remain connected upon removing any one edge if there is no vertex with degree 1. That is, every single vertex has at least two edges. This is because for each vertex u there are at least two edges crossing the cut (u,V-u) and so if one of those edges is removed the graph still remains connected. Conversely, if there is a vertex w with just one edge then there is only one edge crossing the cut (w,V-w) and so removing the edge will make w disconnected from the rest of the graph.

Is my theory correct? If yes, I don’t see how this problem serves as a good variant of problem 18.4 which is about detecting a cycle in a graph.

0 Likes
#2

your argument is wrong. Look at the example below, where each vertex has a degree of > 1
image

0 Likes
#3

There is a solution to this problem which is basically to remove an edge and test if the graph is still connected using dfs, and put the edge back. Do this for all edges. This is O(E*(V+E)) time complexity.

It seems there is another solution that takes O(E+V) here: https://cp-algorithms.com/graph/bridge-searching.html#:~:text=The%20current%20edge%20(v%2Ct,(v%2Cto).

0 Likes