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 Gn+1 un grafo con n + 1 vértices y grado máximo a lo sumo k. Además, supongamos que Gn+1 tiene un vértice, v, de grado menor que k. Solo necesitamos demostrar que Gn+1 es k-coloreable.
Para hacer esto, primero eliminamos el vértice v para producir un grafo, Gn, con n vértices. Al eliminar v, se reduce el grado de todos los vértices adyacentes a v en 1. Entonces en Gn, cada uno de estos vértices tiene grado menor que k. Además, el grado máximo de Gn sigue siendo a lo sumo k. Por lo tanto, Gn cumple con las condiciones de la hipótesis de inducción P(n). Concluimos que Gn es coloreable con k colores.
Una coloreación k de Gn da una coloración de todos los vértices de Gn+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 Gn+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?