Si G es un grafo conexo con un ciclo, si se elimina una arista del ciclo, G sigue siendo conexo.

Question

La prueba es bastante obvia, pero ¿cómo escribirla bien? Me pasa mucho con las pruebas de teoría de grafos, que no sé cómo escribirlas para que sean lo bastante rigurosas.

La prueba en sí sería algo así:

Sea C un ciclo de G. Si eliminamos la arista e = {u, v} de C, entonces C se convierte en un camino entre u y v. C sigue estando conectado, por lo que G sigue estando conectado. C sigue conectado, por lo que G también sigue conectado.

Answer 1

Se nos da que existe un ciclo que contiene la arista $uv$ . Porque $u$ y $v$ forman parte del ciclo hay al menos dos caminos desde $u$ a $v$ : podemos pasar directamente de $u$ a $v$ a lo largo del borde $uv$ o podemos ir en la otra dirección del ciclo y acabar en $v$ . El mismo argumento demuestra que hay al menos dos caminos desde $v$ a $u$ .

Supongamos que $P=x,v_1,\dots v_n,y$ es una ruta desde $x$ a $y$ en $G$ . Si el borde $uv$ no está en $P$ entonces $P$ no cambia si eliminamos $uv$ . Si $uv$ se encuentra en $P$ entonces cuando lleguemos a $u$ podemos dar la vuelta al ciclo para llegar a $v$ y luego seguir $y$ . Dado que esto es cierto para cualquier camino en $G$ concluimos que eliminar $uv$ deja $G$ conectado.

Answer 2

$G$ está conectado $\iff$ cada par de vértices está conectado.

Tomemos dos vértices cualesquiera $u$ y $v$ . Dado que el original $G$ está conectado, podemos elegir un camino entre $u,v$ . Si la arista eliminada no forma parte del camino, entonces en el nuevo grafo, digamos $G'$ Esta vía sigue siendo viable. Si no, como la arista eliminada está en un círculo, podemos sustituirla por el resto del círculo. Por lo tanto, siempre podemos encontrar un camino entre cualquier par de vértices.

Answer 3

Yo escribiría algo así: Que $G$ sea un grafo conexo con un ciclo $C= (c_1, \ldots, c_k)$ . Sea $v_1, v_2$ sean vértices arbitrarios en $G$ y que $(e_1, \ldots, e_n)$ sea un camino desde $v_1$ a $v_2$ (que existe desde $G$ está conectado). Para demostrar que después de eliminar alguna arista $c_j$ del ciclo, el grafo resultante sigue siendo conexo, basta con demostrar que existe un camino $(e_1', \ldots, e'_m)$ de $v_1$ a $v_2$ tal que $e'_i \neq c_j$ para todos $1 \leq i \leq m$ .

Para ello, tenga en cuenta que si $e_i \neq c_j$ para todos $1 \leq i \leq n$ entonces podemos tomar $(e_1', \ldots, e'_m) = (e_1, \ldots, e_n)$ y ya está.

Por lo demás, $e_i = c_j$ para algunos $1 \leq i \leq n$ . Ahora, podemos suponer que $e_i$ es el sólo tal $i$ (o bien podemos definir los caminos como inyectivos, o bien también podemos suponer que $(e_1, \ldots, e_n)$ no tiene aristas que se repitan. Si esto no está claro, pregúntalo). Ahora usamos $C$ es un ciclo, por lo que podemos utilizar las otras aristas del ciclo para sustituir a $c_j$ . Más concretamente, la trayectoria $$ (e_1, \ldots, e_{i-1}, c_{j-1}, c_{j-2}, \ldots, c_1, c_n, c_{n-1}, \ldots,c_{j+1}, e_{i+1}, \ldots, e_n) $$ será una ruta desde $v_1$ a $v_2$ que no contiene $c_j$ . Desde $v_1,v_2$ fueran arbitrarias, con esto concluye la prueba.

Podrías entrar incluso en más detalles (demostrando, por ejemplo, que la ruta dada realmente funciona utilizando la definición de aristas como pares ordenados de vértices), pero a menos que estés en una clase introductoria de demostración o algo así, probablemente querrás menos detalles, no más.