Encontrar un fallo en la prueba de coloración k falsa

Question

Sigo un curso de matemáticas discretas de MIT, una de las tareas plantea el problema de encontrar el error en una demostración de $k$-coloración (el curso solo considera grafos simples sin bucles):

Afirmación Falsa. Sea $G$ un grafo (simple) con grado máximo a lo sumo $k$. Si $G$ también tiene un vértice de grado menor que $k$, entonces $G$ es $k$-coloreable.

a) Da un contraejemplo a la Afirmación Falsa cuando $k = 2$.

Tal vez estoy simplificando demasiado el problema, pero dice "... Si $G$ también tiene un vértice de grado menor que $k$ ...", eso significa que $G$ solo necesita tener al menos un nodo con grado menor al grado máximo $k$.

Así que para responder a a), pensé en este grafo:

El grado máximo aquí es 2 y también tiene un nodo que tiene un grado menor que 2, pero aún necesitas $k+1$ colores para colorearlo, por lo que la afirmación no puede ser cierta en este caso.

Luego, también proporcionan una prueba falsa para la afirmación:

Identifica la oración exacta donde la prueba falla.

Hipótesis de inducción: P(n) se define como: Sea un grafo $G$ con $n$ vértices y grado máximo a lo sumo $k$. Si $G$ también tiene un vértice de grado menor que $k$, entonces $G$ es $k$-coloreable.

Caso base: ($n=1$) $G$ tiene solo un vértice y por lo tanto es coloreable con 1 color. Así que P (1) es verdadero.

Paso inductivo: Podemos asumir $P(n)$. Para probar $P(n + 1)$, sea $G_{n+1}$ un grafo con n + 1 vértices y grado máximo a lo sumo k. Además, supongamos que $G_{n+1}$ tiene un vértice, $v$, de grado menor que k. Solo necesitamos demostrar que $G_{n+1}$ es $k$-coloreable.

Para hacer esto, primero eliminamos el vértice v para producir un grafo, $G_n$, con n vértices. Al eliminar v, se reduce el grado de todos los vértices adyacentes a v en 1. Entonces en $G_n$, cada uno de estos vértices tiene grado menor que k. Además, el grado máximo de $G_n$ sigue siendo a lo sumo k. Por lo tanto, $G_n$ cumple con las condiciones de la hipótesis de inducción $P(n)$. Concluimos que $G_n$ es coloreable con k colores.

Una coloreación k de Gn da una coloración de todos los vértices de $G_{n+1}$, excepto v. Dado que v tiene grado menor que k, habrá menos de k colores asignados a los nodos adyacentes a v. Así que entre los k colores posibles, habrá un color no utilizado para colorear estos nodos adyacentes, y este color se puede asignar a v para formar una coloración de $G_{n+1}$.

Necesitamos identificar dónde falla la prueba. Esta me resulta un poco más difícil, ya que la prueba es relativamente larga.

Para mí, el caso base parece incorrecto. Dice:

Caso base: (n=1) G tiene solo un vértice y por lo tanto es coloreable con 1 color. Así que P (1) es verdadero.

Es cierto que puedes colorear un grafo de un solo nodo con un solo color. Pero la afirmación habla de un grafo que tiene un grado a lo sumo k (que es 0 en un grafo de un solo nodo) y que también tiene un vértice con un grado menor que k (que sería -1 o menos?), pero el único nodo en ese grafo tiene grado k (que es 0 y es igual al grado máximo de ese grafo que también es 0).

¿Estoy en el camino correcto o la prueba falla en otro lugar?

Answer 1

Su contraejemplo no es correcto, ya que tiene grado máximo de $3$. Pista: piense en grafos desconectados.

El problema con la demostración no es el caso base, ese está bien (estás haciendo inducción en $n$, no en $k$, por lo que $k$ está fijo y podría ser mucho mayor que el grado máximo para casos pequeños). El problema es que cuando eliminan un vértice $v$, dicen que cada uno de sus vecinos ahora tendrá grado menor que $k$. ¿Qué pasa si no tenía ningún vecino?

Answer 2

Especialmente la respuesta de Lime cubre básicamente todo, también el comentario de TMM tiene mucho sentido. Como quería dibujar un gráfico nuevamente, aquí está mi respuesta actualizada al problema:

Así que en este gráfico tenemos el grado máximo $k = 2$, y también un nodo con un grado menor que $k$ pero aún necesita $k + 1 = 3$ colores.

De hecho, el caso base está bien, porque el grafo de un solo nodo se puede colorear en $k$ colores, eso es solo un hecho y estamos haciendo inducción en el número de vértices, así que está bien. Estaba interpretando el caso base demasiado literalmente.

Ahora, donde la demostración se equivoca, creo que hay dos formas de verlo:

• como dijo TMM, si decimos "Además, supongamos que $G_{n + 1}$ tiene un vértice, $v$, de grado menor que $k$. [...] Para hacer esto, primero quite el vértice $v$ para producir un grafo, $G_n$ [...]" pero si el grafo solo tenía un vértice de ese tipo y lo eliminamos, entonces no podemos hacer uso de P(n). Eso significaría que la demostración se equivoca en "Así que $G_n$ cumple con las condiciones de la hipótesis de inducción P(n)"
• como dijo Especialmente Lime, si pensamos en un grafo como se muestra arriba con nodos desconectados, "Eliminar $v$ reduce el grado de todos los vértices adyacentes a $v$ en 1." no funciona porque si $v$ está desconectado, no hay nodos adyacentes a $v$ y por lo tanto el grado de todos los demás nodos en el grafo no se ve afectado al eliminar $v$.