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?
