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