Demostrar que si cada nodo de un grafo simple $G$ tiene grado $3$ o superior, entonces $G$ contiene un ciclo con un acorde.

Question

Por gráfico simple entiendo un gráfico sin bucles ni aristas dobles.

Si $C$ es un ciclo y $e$ es una arista que conecta dos nodos no adyacentes de $C$ entonces $e$ se llama acorde.

Me doy cuenta de que un plan de ataque es elegir cualquier nodo, digamos $v_0$ . Entonces, como el grado de $v_0$ es $3$ hay $3$ otros nodos conectados a él. Repitiendo este argumento tendremos que llegar eventualmente a un nodo que esté conectado por una arista a uno de los nodos utilizados anteriormente.

No veo cómo esto garantiza la existencia de un acorde.

Answer 1

Pista 1: por inducción en $n$ el número de nodos. El caso $n=4$ es fácil. ¿Y el paso de la inducción?

Mira que sólo si no se te ocurren ideas:

Pista 2:

Si se "fusionan" dos nodos de dicho gráfico, ¿qué ocurre?

Solución (sólo en caso de gran emergencia...)

Dejemos que $P(n)$ denota: cada nodo, en un gráfico simple $G$ con $n$ nodos, tiene grado 3 o superior, implica que $G$ contiene un ciclo con un acorde.

$P(4)$ es trivialmente cierto.
El único grafo simple de grado al menos 3 es el grafo totalmente conexo.

Supongamos que $P(n)$ Es cierto.
Dejemos que $G$ sea un grafo simple de al menos un grado $3$ con $n+1$ nodos.

Llamamos a la fusión de dos nodos $n_1$ y $n_2$ la eliminación de $n_1$ y $n_2$ y la adición de un nuevo nodo $f$ tal que cada arista de entrada/salida de $n_1$ y $n_2$ son ahora bordes de entrada/salida de la nueva fusión $f$ y luego eliminar los "bordes dobles" y los bucles propios.

Fusionar dos nodos vecinos tales que tengan (al menos) un vecino no en comón para obtener $G'$ un grafo simple de grado mínimo $3$ con $n$ nodos. Si estos nodos no existen, significa que tu grafo está totalmente conectado (o está formado por varias partes totalmente conectadas) y la propiedad es trivial.
De lo contrario, por $P(n)$ sabes que contiene un ciclo con un acorde.
Dos casos:
- o bien el ciclo no contiene $f$ entonces este ciclo aparece en $G$ por lo que $P(n+1)$ se mantiene.
- O el ciclo contiene $f$ , despliega este ciclo en el ciclo que contiene $n_1$ y $n_2$ y tienes un ciclo en $G$ y el cable sigue presente (ya sea conectando uno de los $n_i$ u otros nodos).
Por lo tanto, $P(n+1)$ También tiene.