demostrar que un grafo conexo con $n$ vértices tiene al menos $n-1$ bordes

Question

Demuestre que todo grafo conexo con $n$ vértices tiene al menos $n 1$ bordes.

¿Cómo puedo demostrarlo? Conceptualmente, entiendo que el siguiente grafo tiene 3 vértices, y dos aristas:

a-----b-----c

con $a$ , $b$ y $c$ siendo vértices, y $\{a,b\}$ , $\{b,c\}$ siendo bordes.

¿Hay alguna forma de demostrarlo lógicamente?

--UPDATE--

¿Le parece correcto? Agradecería cualquier consejo sobre cómo mejorar esta prueba. Muchas gracias.

Answer 1

Un gráfico con $v$ vértices y $e$ bordes tiene al menos $v-e$ componentes conectados.

Prueba: Por inducción en $e$ . Si $e=0$ entonces cada vértice es un cmoponente conectado, por lo que la afirmación se cumple. Si $e>0$ elige un borde $ab$ y que $G'$ sea el gráfico obtenido eliminando $ab$ . Entonces $G'$ tiene como máximo un componente más que $G$ (es decir, si $a$ y $b$ ya no están en el mismo componente en $G'$ ). Por hipótesis de inducción, $G'$ tiene al menos $v-(e-1)$ componentes, por lo que $G$ tiene al menos $v-(e-1)-1=v-e$ componentes como se iba a demostrar.

Answer 2

Existen dos enfoques estándar:

1. Utilizar el árbol de expansión (y el hecho de que cualquier árbol de $n$ vértices tiene exactamente $n-1$ bordes).

2. Inducción sobre el tamaño del grafo. Supongamos que tenemos un grafo conexo de $n$ vértices y $m$ bordes. Elimina las aristas hasta que tu grafo se divida en dos partes. Por hipótesis inductiva ambas partes tienen al menos $n_1 - 1$ y $n_2 - 1$ bordes (donde $n_1+n_2 = n$ ), por lo que su gráfico tenía al menos $n_1 -1 + n_2 - 1 + 1 = n - 1$ aristas (la adicional denota la última arista que eliminaste antes de que el grafo dejara de estar conectado).

Espero que esto ayude $\ddot\smile$

Answer 3

Sea $V = \{v_1, v_2, \dots, v_n\}$ sea el conjunto de vértices y consideremos el $n \times (n-1)$ triángulo

$$ \begin{eqnarray} (v_1, v_2) & (v_1,v_3) & \cdots & (v_1, v_n) \\ & (v_2, v_3) & \cdots & (v_2,v_n) \\ & & & \; \; \; \; \vdots \\ & & & (v_{n-1}, v_n) \end{eqnarray}$$ donde cada punto está asociado a una arista potencial. Rodea con un círculo una entrada, por ejemplo, si el gráfico tiene una arista. Si hay estrictamente menos de $n-1$ bordes, porque hay $n-1$ filas debe haber una de ellas sin aristas. Pero una fila es de la forma $(v_i, v_j)$ , $i<j$ y que no tenga bordes significa $v_i$ no está conectado. Pero esto significa que el gráfico no está conectado. Así que hay al menos $n-1$ bordes.

Answer 4

Sea G sea un grafo conexo : Si G no tiene ciclos, entonces G está conectado sin ciclos $=> G$ es un Árbol. Así que $G$ tiene n-1 aristas.

Si G tiene ciclos : y $G $ está conectado, entonces para cada dos vértices hay un camino entre ellos. Suponiendo que $G$ tienen un solo ciclo: veamos el camino : $ v_1,v_2 \dots v_n,v_1 $ podemos eliminar la arista $ v_1,v_1$ y obtendremos un subgrafo conectado $ v_1,v_2$ sin ciclos y $E(H)+1 =E(G)$ así que $E(G)=n$ .

Y por inducción se obtendrá que para cada número de ciclos n $E(G)\ge n$ .

Así que si $G $ tiene ciclos $E(G)=n-1$ si no $E(G)\ge n$ .

Answer 5

Este resultado es inmediato por inducción una vez que se ha establecido (como lema) que en todo grafo conexo con al menos dos vértices hay al menos dos vértices que se pueden eliminar individualmente (con todas las aristas adyacentes) de forma que el grafo restante sigue siendo conexo. (El propio lema se demuestra a su vez mediante una inducción bastante sencilla sobre el número de vértices.