Let $G = (V, E)$ be connected graph with at least three vertices. How would one proof that $G$ contains vertices $u, v \in V$ such that all three graphs: $G$ without $v$, G without $u$, G without $u$ and $v$ are also connected.
Should I do it by using an induction in some way? Or by "taking vertices away from graph"?
If $G$ is connected it has a spanning tree, since it has at least two vertices the spanning tree has at least two leaves. select two of them. Those leaves satisfy what you want in the tree. Since the entire graph only has more edges, it also satisfies what you want in the original graph.