Is a graph still connected if we remove $2$ nodes? Let $G=(V,E)$ be a connected graph, $|V| \geq 2$.
I want to show that there are at least $2$ nodes $x,y \in V$ such that $G, G-x$ and $G-y$ have the same number of connected components.
Now, since $G$ is in itself a connected graph, it has exactly $1$ connected component. So if the statement is true, it must be that $G-x$ and $G-y$ also have only one connected component, so they are connected.
But I'm having trouble proving it, and also it seems to defy logic. If it really does turn out that in ANY connected graph there are $2$ nodes that I can remove and still get a connected graph, I would be very surprised.
 A: I think I have a neat proof, which avoids any kind of induction.

Lemma
Let $G = (V,E)$ be a connected finite graph. For any $z \in V$, let $x \in V$ be such that:
$$d(z,x) = \max_{y \in G} d(z,y).$$
Then $G - x$ is connected.

Proof
Let $G$, $z$ and $x$ be as in the hypotheses of the lemma.
Let $y_1$ and $y_2$ be in $V - \{x\}$. Since $G$ is connected, there exists a minimal path in $G$ between $y_1$ and $z$, as well as between $y_2$ and $z$. These paths cannot go through $x$; otherwise, we would get $d(z,x)<d(z,y_1)$. Hence, these are paths in $G - x$. By concatenation, we get a path between $y_1$ and $y_2$ in $G-x$
Hence, $G-x$ is connected $\square$
Now, take any $z \in G$. Find $x$ which maximizes $d(z,\cdot)$. By the lemma, $G-x$ is connected. Then, find $y$ which maximizes $d(x,\cdot)$. By the lemma, $G-y$ is connected. Since $G$ has at least two vertices, $x$ and $y$ are different.
A: Idea. Use induction. Take a $z \in G$.
$G-z$ is either connected or not connected. If connected, then there are $x, y$ such that $(G-z) - x, (G-z) - y$ are connected by induction. What does that tell us about $G-x$ and $G-y$?
If not connected, let $S, T$ be the connected components of $G - z$. If either $S$ or $T$ has only one vertex, then we can instead remove that single vertex $s$ making up $S$  (or $t$ making up $T$) from $G$ and then $G-s$ (or $G-t$) is connected. To find the second $G-y$, we note that $(G-s)-x$ is connected by induction for some $x$ and we proceed as above.
Otherwise, we have $S$ and $T$ have at least two vertices. Again by induction they have two points such that $S-s_1, S-s_2, T-t_1, T-t_2$ are connected. What do we know about $z$'s connection to any of these graphs?
