¿Sigue siendo un gráfico conectado si eliminamos $2$ ¿Nodos?

Question

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.

Answer 1

Creo que tengo una prueba clara, que evita cualquier tipo de inducción.

Lema

Dejemos que $G = (V,E)$ sea un grafo finito conectado. Para cualquier $z \in V$ , dejemos que $x \in V$ sea tal que:

$$d(z,x) = \max_{y \in G} d(z,y).$$

Entonces $G - x$ está conectado.

Prueba

Dejemos que $G$ , $z$ y $x$ sea como en las hipótesis del lema.

Dejemos que $y_1$ y $y_2$ estar en $V - \{x\}$ . Desde $G$ está conectado, existe un camino mínimo en $G$ entre $y_1$ y $z$ así como entre $y_2$ y $z$ . Estos caminos no pueden pasar por $x$ de lo contrario, obtendríamos $d(z,x)<d(z,y_1)$ . Por lo tanto, se trata de caminos en $G - x$ . Por concatenación, obtenemos un camino entre $y_1$ y $y_2$ en $G-x$

Por lo tanto, $G-x$ está conectado $\square$

Ahora, toma cualquier $z \in G$ . Encuentre $x$ que maximiza $d(z,\cdot)$ . Por el lema, $G-x$ está conectado. Entonces, encuentra $y$ que maximiza $d(x,\cdot)$ . Por el lema, $G-y$ está conectado. Como $G$ tiene al menos dos vértices, $x$ y $y$ son diferentes.

Answer 2

Idea. Utilizar la inducción. Tome una $z \in G$ .

$G-z$ está conectado o no está conectado. Si está conectado, entonces hay $x, y$ tal que $(G-z) - x, (G-z) - y$ están conectados por inducción. ¿Qué nos dice eso sobre $G-x$ y $G-y$ ?

Si no está conectado, deje que $S, T$ sean las componentes conectadas de $G - z$ . Si cualquiera de los dos $S$ o $T$ sólo tiene un vértice, entonces podemos eliminar ese único vértice $s$ componiendo $S$ (o $t$ componiendo $T$ ) de $G$ y luego $G-s$ (o $G-t$ ) está conectado. Para encontrar el segundo $G-y$ observamos que $(G-s)-x$ está conectada por inducción para algún $x$ y se procede como en el caso anterior.

De lo contrario, tenemos $S$ y $T$ tienen al menos dos vértices. De nuevo por inducción tienen dos puntos tales que $S-s_1, S-s_2, T-t_1, T-t_2$ están conectados. ¿Qué sabemos sobre $z$ ¿conectas con alguno de estos gráficos?