I would like to know if proof below is correct for this problem.
Let $n$ be the number of vertices of the graph $G$.
As $G$ is connected graph, that means there are at least $n-1$ edges in the graph.
- If $G$ has exactly $n-1$ edges and $n$ vertices, it is a tree. Tree has at least two leaves. Let $u$ and $v$ be those leaves. By removing a vertex of degree 1 from a connected graph, it stays connected. That means $G-u$ and $G-v$ are connected too.
- If $G$ has more than $n-1$ edges, and it is connected, we can construct a spanning tree for all the vertices of the graph $G$. That spanning tree also has at least two leaves. Let $u$ and $v$ be those leaves. These vertices are either leaves in $G$ or are connected with some another vertex in $G$ so they make a cycle. Either way, $G-u$ is connected, so is $G-v$.
Thanks :)