# How to prove that 3-coloring is decidable?

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.

• This is good enough for me. By the way, even if you want to be very formal you don't have to provide a Turing machine; a program in any Turing-complete language will suffice. (Indeed, the language need not even be Turing-complete, we just need it to define computable functions.) Jan 1 '16 at 20:53
• For most people it does. In an introductory course it might not. Also, for some people "formal proof" means something different, which you might have seen if you took a course on logic. Jan 1 '16 at 21:52
• @YuvalFilmus Thanks. What does a "formal proof" in the context of a logic course look like, would you be able to point me to an example please? Jan 2 '16 at 3:19
• @Jenny If you're interested, take a logic course. Jan 2 '16 at 11:56
• @YuvalFilmus I don't have access to a logic course, is there a book or an online source you can recommend? Jan 2 '16 at 13:01

All the non deterministical problems for TM are decidable, so from your description you demonstrated you needed $3^{n}$ turing machines to validate a solution. So your explanation is enough.