# Every connected graph on more than 3 vertices has two vertices whose removal doesn't disconnect it

Prove that every undirected connected graph with $|V| > 2$ has at least two vertices such that if one or both are removed (along with their incident edges) the resulting graph is still connected. Describe an efficient algorithm to find two such vertices.

How would I go about solving this?

• What did you try? Where did you get stuck? We're happy to help you understand the concepts but just solving exercises for you is unlikely to achieve that. See also meta.cs.stackexchange.com/q/1284/755. – D.W. Nov 21 '16 at 17:31