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.

• Re: intuition: I was surprised by the statement as well until I started working with some examples. If the graph happens to be a tree, we know there are two leaves, so just take them away. In general, a graph might not have enough leaves, so this doesn't immediately prove the result. But since trees are "minimal" connected graphs, we might expect to do the same in general. Perhaps you can leverage one of the "minimality" results about trees to patch the argument into a full proof. – Eric Stucky Nov 16 '15 at 9:52
• Trees are a good example, but as you said, not every graph is a tree. So...yeah – Oria Gruber Nov 16 '15 at 9:57
• Side remark: $V$ needs to be finite for the statement to be true. Otherwise, consider an infinite tree whose degrees are all different. – D. Thomine Nov 16 '15 at 10:13
• Why do the degrees need to be different? Seems like any infinite tree would work; $\Bbb Z$ in particular... – Eric Stucky Nov 16 '15 at 10:24
• @Eric Stucky: because then, the initial statement ("There exist distinct $x$ and $y$ such that $G-x$ and $G-y$ have the same number of connected components") could still be true. – D. Thomine Nov 16 '15 at 11:16

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.

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?