In order to prove that 3-coloring is decidable, is it sufficient to say:
- Each node in the graph has 3 possible colors
- Therefore we can enumerate over all $3^n$ possibilities and then check that no two edges connect nodes with the same color
Does that prove that 3-coloring is decidable? Or do I need to construct a Turing machine for a proper proof?
By 3-coloring I'm talking about the graph coloring problem; i.e. assign one of 3 colors to each node in an undirected graph such that no two adjacent nodes have the same color.