Prueba de que todo grafo simple conexo tiene al menos 2 vértices no cortados.

Question

Intento demostrar que cualquier grafo simple conectado con al menos $3$ vértices ( $|V| \ge 3$ ) tiene al menos $2$ vértices cuya eliminación no conducirá al incremento del número de componentes. En otras palabras, hay al menos $2$ vértices que son vértices no cortados.

Intento de solución:

Intenté demostrarlo usando la inducción por el número de vértices: $n - t \ge 2$ , donde $n$ es el número de vértices que tiene nuestro gráfico, y $t$ es un número de vértices cortados.

1. Base
   Dejemos que $n =3$ Entonces el gráfico tendrá el siguiente aspecto: $--$
   Está claro que tiene un vértice cortado (el del medio). Por lo tanto, $3-1 \ge 2$ se mantiene.
   O puede ser un gráfico completo, entonces $3 - 0 \ge 2$ también tiene.

2. Supuesto
   Dejemos que $n = k$ y la fórmula se mantiene, $k - t >= 2$

3. Paso
   Prueba para $n = k + 1$
   Si añadimos un vértice al grafo, puede ser un vértice cortado o no cortado. En caso de que sea un vértice cortado, tenemos
   $$\begin{align*}&(k+1) - (t+1) \ge 2\\ &k + 1 - t - t\ge 2\\ &k\ge 2\end{align*}$$

En caso de que no sea un vértice cortado... y estoy atascado aquí, porque puede pasar cualquier cosa. El número de vértices cortados podría aumentar, podría disminuir, o permanecer igual.

Estoy seguro de que hay una prueba mejor y más corta para esto, y realmente espero que alguien pueda ayudarme.

Answer 1

Creo que el resultado se desprende del hecho de que todo grafo conectado tiene un árbol de expansión y todo árbol con más de un vértice tiene al menos dos hojas.

(Por cierto, si quieres demostrar esto por inducción en $k$ , entonces en el paso 3 no deberías empezar con un $k$ -y añadirle un vértice. Estás tratando de demostrar alguna propiedad de $(k+1)$ -de vértices, por lo que hay que empezar con un $(k+1)$ -gráfico de vértices; entonces se puede optar por quitar un vértice y utilizar la hipótesis de inducción).

Answer 2

Dejemos que $G$ sea un grafo conexo de orden 3 o más, y sea $u$ y $v$ sean dos vértices de $G$ cuya distancia entre sí, $l$ es igual al diámetro de $G$ , $d(u,v) = diam(G)=l$ . Afirmamos que ni $u$ ni $v$ son vértices de corte de $G$ .

Supongamos, por el contrario, que uno de $u$ y $v$ , digamos que $u$ es un vértice de corte de $G$ . Entonces, en $G-u$ hay un vértice $x$ en un componente diferente de $v$ . Así, en $G$ , $u$ mentiras en cada $v-x$ camino.

Ahora, dejemos que $P$ sea el más corto $v-x$ camino en $G$ . Desde $P$ contiene $u$ , $d(v, x) > d(v,u)$ que es imposible.

Answer 3

Este es un argumento de la Introducción a la Teoría de Grafos de Douglas West (con muy ligeros comentarios por mi parte).

Dejemos que $G$ sea un gráfico simple (West asume $G$ es un gráfico con una arista que no es de bucle). Entonces existe un camino máximo $P$ en $G$ con punto final $u$ . Obsérvese que todos los vecinos de $u$ debe estar en $P$ , en caso contrario, si $u$ tiene algún vecino que no está en $P$ , entonces podríamos ampliar $P$ pero $P$ es máxima. Así que $P-u$ está conectado en $G-u$ y todos los vecinos de $u$ todavía se encuentran en $P-u$ (es decir, sigue habiendo un camino entre cualquier $2$ de $u$ ), por lo que $G-u$ está conectado. Como $P$ tiene $2$ puntos finales, $G$ tiene al menos $2$ vértices no cortados.