Dejemos que $G=(V,E)$ sea un gráfico conectado, $|V| \geq 2$ .
Quiero demostrar que hay al menos $2$ nodos $x,y \in V$ tal que $G, G-x$ y $G-y$ tienen el mismo número de componentes conectados.
Ahora bien, como $G$ es en sí mismo un gráfico conectado, tiene exactamente $1$ componente conectado. Por tanto, si la afirmación es cierta, debe ser que $G-x$ y $G-y$ también tienen un solo componente conectado, por lo que están conectados.
Pero tengo problemas para probarlo, y además parece desafiar la lógica. Si realmente resulta que en CUALQUIER gráfico conectado hay $2$ nodos que pueda eliminar y seguir obteniendo un gráfico conectado, me sorprendería mucho.