Demostrar/desprobar que todo grafo finito no dirigido $G = (V,E)$ con $n$ vértices $ \forall v \in V$ : $deg(v) \ge 1$ es un gráfico conectado

Question

Una arista está asociada a dos vértices.

Trato de contradecirlo diciendo que el gráfico está desconectado.

Utilizando el lema del apretón de manos, en el gráfico hay al menos $\frac{n}{2}$ bordes.

Hay $k\ge2$ componentes conectados, por lo que existe un componente conectado que tiene como máximo $\frac{n}{k}$ vértices.

No sé cómo continuar...

¿Cómo puedo demostrarlo?

Gracias.

Answer 1

Vértices dados $v_1,\ldots,v_n$ (donde $n \ge 4$ ), forman un gráfico con dos componentes conectados, donde el primer componente es la arista $v_1 v_2$ y el segundo componente es un gráfico de trayectorias $v_3, \ldots, v_n$ . Debido a este contraejemplo, la afirmación dada es falsa si $|V| \ge 4$ .

Answer 2

Si se toma el gráfico $G$ con $V = \{1,2,3,4,...,2n-1,2n\}$ y conectar $1\sim 2$ , $3\sim 4$ , $5\sim 6$ , . . . $(2n-1)\sim2n$ entonces $\deg(v) \geq 1$ para todos $v$ pero $G$ no está conectado.