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.


If your graph is connected, then you always have a Spanning Tree, now you can reduce the problem to proving that Every Finite Non-Trivial Tree has at Least 2 Leaf Nodes.


  Describe an efficient algorithm to find two such vertices.


A very obvious way would be just to find 2 leaf nodes of your Spanning Tree.