Consideremos la siguiente prueba por inducción:
Teorema. Todos los árboles son $2$ -Colable.
Prueba. Introducimos en $n$ el número de vértices del árbol. Cuando $n=1$ podemos dar al único vértice el color que queramos.
Supongamos que todos los $n$ -Los árboles de vértices son $2$ -colable. Para demostrar esto para $(n+1)$ -árboles de vértice, tomar un $n$ -árbol de vértices $T$ , $2$ -colorarlo, y luego añadir un $(n+1)^{\text{th}}$ vértice $v$ conectado por una arista a cualquier vértice de $T$ . El árbol resultante $T+v$ puede ser $2$ -coloreado por dar $v$ el color opuesto al del vértice al que acabamos de conectarlo.
Por inducción, el teorema se cumple para todo $n$ .
Esta no es una prueba muy buena, pero se puede hacer que funcione si se aclara una suposición no establecida: cualquier $(n+1$ )-árbol de vértices se puede obtener añadiendo a un $n$ -(He visto que un libro de texto llama a esto "Procedimiento de crecimiento del árbol", posiblemente sólo por el juego de palabras).
La hipótesis correspondiente es no es cierto para todo tipo de gráficos, y asumir que siempre es cierto nos lleva a errores clásicos como:
Teorema. Todos los gráficos planos son $4$ -Colable.
No es a prueba. Basta con colorear todo máximo (triangulados) gráficos planos, porque siempre podemos añadir aristas a un gráfico plano para triangularlo, y una coloración adecuada de la triangulación es también una coloración adecuada del gráfico original.
Lo demostramos por inducción en $n$ . Para $n \le 4$ , a $4$ -La coloración existe porque podemos dar a cada vértice su propio color.
Supongamos que todos los $n$ -Las triangulaciones planas de vértice son $4$ -colable. Para demostrar esto para $(n+1)$ -triangulaciones planas de vértice, tomar un $n$ -Vértice uno y añadirle otro vértice, dibujando todas las aristas posibles.
El nuevo vértice se ha añadido en el centro de una cara (triangular), por lo que está conectado a tres vértices de ese triángulo. El $n$ -el gráfico de vértices tenía un $4$ -coloración por la hipótesis inductiva, que podemos extender a una coloración del nuevo grafo dando al nuevo vértice un color diferente de cualquiera de los tres colores utilizados para esos vértices.
Por inducción, el teorema se cumple para todo $n$ .
(Posiblemente no estoy haciendo el argumento muy convincente porque sé que está mal, pero las variantes de este error son muy comunes entre los estudiantes que aprenden por primera vez la teoría de grafos).
Mi pregunta: ¿existe una palabra para designar las familias de grafos (o de objetos combinatorios en general; esta cuestión no se limita a la teoría de grafos) para las que existe un "Procedimiento de Crecimiento", y este tipo de argumento funciona? ¿Existe una teoría de cuándo existen "Procedimientos de Crecimiento"?
