Why isn't 3-color in P?

Question

I feel like I'm missing something here, but no graph with degree greater than 3 will ever be able to be colored with 3 colors.

Doesn't this mean the problem is solvable through a linear pass of the vertices, checking the degrees?

I must be misunderstanding something, I know 3-colorable must reside in NP, but why can't you just check the degrees?

Answer 1

Sorry, I know it's looked down upon to answer one's own question, but I figured out my mistake:

No graph that contains a 4-clique will ever be 3-colorable, but there are graphs that contain degree >= 3 that are 3-colorable.

Take this counter-example:

   - 2 -
 /       \
1  - 2 -  1
 \       /
   - 2 -

Notice how the "1"s have degree >= 3 but the graph itself is still 3-colorable.

Answer 2

What you are missing is that not every graph with all nodes having either one or two edges can be coloured in three colours.