[Solved]: How to prove that 3-coloring is decidable?

Problem Detail: 

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.

Asked By : Jenny

Answered By : David Richerby

It depends entirely on what level of formality you're aiming for. The informal description of an algorithm in your question is quite enough to convince me that 3-colourability is decidable. If you wanted to be a bit more formal, you could give pseudocode. If you wanted to be more formal still, you could describe a Turing machine in English. If you wanted to be even more formal, you could write down the full description of the Turing machine and prove that it really does decide 3-colourability.

Having said that, of the options I've listed, it's way more likely that there'd be an error in the description of the Turing machine or in its correctness proof! So it's not clear which proof would be the most believable.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/51355