$G$ tiene exactamente $n-1$ implica que cada arista de $G$ es un puente

Question

Dejemos que $G$ sea un grafo simple conectado en $n$ vértices. Demuestre que $G$ tiene exactamente $n-1$ implica que cada arista de $G$ es un puente.

La afirmación anterior es obviamente cierta. Algunos libros de texto incluso utilizan esta afirmación como definición de árbol. Sin embargo, mi profesor nos propone demostrarlo directamente como ejercicio. Sería estupendo que pudieras verificar mi prueba de abajo y/o dar otra prueba directa de la afirmación.

---

La última versión:

Procedemos por inducción en $n$ el número de vértices de $G$ . Para el caso $n=2$ , $G$ tiene 2 vértices y 1 arista. Está claro que esta arista es un puente.

Supongamos que $G$ tiene $n$ vértices y exactamente $n-1$ bordes. Afirmamos que debe existir un vértice $v$ con $\text{deg}(v)=1$ . Si la reclamación no es correcta, entonces $$n-1 = \text{number of edges} = \frac{1}{2} \times \text{sum of degree} \geq \frac{1}{2} \times 2n=n$$ que es una contradicción. Por lo tanto, tal $v$ existe, con una sola arista $\alpha$ incidente a la misma. Ahora, en la eliminación de $\alpha$ , $G$ se divide en dos componentes conectados $G_1$ y $G_2$ . En particular, $G_1=\{v\}$ es un singleton. Por lo tanto, $\alpha$ es un puente. Por hipótesis de inducción, $G_2$ tiene $n-1$ vértices y exactamente $n-2$ aristas, por lo que cada arista en $G_2$ es un puente. Por lo tanto, cada arista en $G$ es un puente.

---

Versión incorrecta:

Procedemos por inducción en $n$ el número de vértices de $G$ . Para el caso $n=2$ , $G$ tiene 2 vértices y 1 arista. Está claro que esta arista es un puente.

Supongamos que $G$ tiene $n-1$ vértices y exactamente $n-2$ bordes. Por la hipótesis de inducción, estas $n-2$ Los bordes son puentes. Ahora, elegimos un vértice arbitrario en G, lo unimos a un vértice recién añadido $v$ por un borde $\alpha$ . Queda por demostrar $\alpha$ es un puente. Tenga en cuenta que, al retirar $\alpha$ el gráfico quedará desconectado, ya que no habrá ninguna arista incidente en $v$ . Por lo tanto, $\alpha$ es efectivamente un puente y hemos terminado.

Answer 1

Otra prueba por contradicción sería:

Supongamos que $G=(V,E)$ es un gráfico conectado con $|V|=n$ y $|E|=n-1$ y $G$ tiene al menos una arista $e_B$ que no es un puente. Sabemos que una arista es un puente si y sólo si no está contenida en un ciclo. Como $e_B$ es un puente, $e_B$ tiene que ser parte de un ciclo entre algunos vértices $V_1=\{v_1,...,v_k\}$ . Se deduce que estos vértices tienen que estar conectados con al menos $k$ bordes.

Ahora miramos el $n-k$ vértices restantes $V_2=\{v_{k+1},...,v_n\}$ . Desde $k$ Las aristas forman parte del ciclo descrito anteriormente y sólo conectan algunos vértices de $V_1$ no puede haber más de $|E|-k=n-k-1$ aristas que se conectan entre los vértices de $V_2$ .

Sabemos que al menos $m-1$ bordes son necesarios para conectar $m$ vértices. $n-k-1$ bordes y $n-k$ vértices no forman parte del ciclo, sino porque al menos un vértice de $V_2$ tiene que estar conectado a un vértice de $V_1$ (porque si no, $G$ no estaría conectado), al menos $n-k-1+1=n-k$ bordes que no forman parte del ciclo serían necesarios para $G$ para ser conectado. Por lo tanto, $G$ no se puede conectar. $\square$

He tenido algunos problemas para expresar mis pensamientos, así que no dudes en comentar si algo no está claro.