AlanTuring

Hi so i am preparing for my algorithms class exam and this question is the second last one in my text book with graphs, and i am not too sure how to obtain an algorithm that is just O(m+n). a) Prove that every connected graph G=(V,E) has a node v∈V such that removing v and all its adjacent edges will not disconnect G. (b) For a given connected graph G=(V,E), design an O(n+m)-time algorithm to find such a node. I have understood that i need to take a case such as say for nodes v,w there is a node in between the path from v to w such that if v - x - w is the path, and x is removed, the graph is still connected. Anyone have any ideas? TIA.

Hi so i am preparing for my algorithms class exam and this question is the second last one in my text book with graphs, and i am not too sure how to obtain an algorithm that is just O(m+n). a) Prove that every connected graph G=(V,E) has a node v∈V such that removing v and all its adjacent edges will not disconnect G. (b) For a given connected graph G=(V,E), design an O(n+m)-time algorithm to find such a node. I have understood that i need to take a case such as say for nodes v,w there is a node in between the path from v to w such that if v - x - w is the path, and x is removed, the graph is still connected. Anyone have any ideas? TIA.