I am working on the following problem:
Let G be a connected graph of order at least two. Show that there are two vertices $u$ and $v$ such that both G - $u$ and G - $y$ are connected.
My thoughts:
Since G is connected, we know that it contains a spanning tree. We can clearly delete a leaf of this spanning tree and G will remain connected. I am pretty sure that if $|G| > 2$, then the spanning tree of G must contain two leaves that we can delete (w/o affecting connectivity, of course), but I am not sure how to formally prove this.
