¿Cómo demostrar que 3 colores es decidible?

Para demostrar que 3 colores es decidible, ¿es suficiente decir:

• Cada nodo en el gráfico tiene 3 colores posibles.
• Por lo tanto, podemos enumerar las posibilidades y luego verificar que no haya dos bordes conectando nodos con el mismo color$3^n$

¿Eso prueba que 3 colores es decidible? ¿O necesito construir una máquina de Turing para una prueba adecuada?

Por 3 colores, estoy hablando del problema de color del gráfico; es decir, asigne uno de los 3 colores a cada nodo en un gráfico no dirigido de modo que no haya dos nodos adyacentes que tengan el mismo color.

Depende completamente de qué nivel de formalidad esté buscando. La descripción informal de un algoritmo en su pregunta es más que suficiente para convencer a mí que el 3-colorabilidad es decidible. Si quisieras ser un poco más formal, podrías dar un pseudocódigo. Si aún quisiera ser más formal, podría describir una máquina de Turing en inglés. Si desea ser aún más formal, puede escribir la descripción completa de la máquina Turing y demostrar que realmente decide la capacidad de 3 colores.

Dicho esto, de las opciones que he enumerado, es mucho más probable que haya un error en la descripción de la máquina Turing o en su prueba de corrección. Por lo tanto, no está claro qué prueba sería la más creíble.

$3^{n}$