[danbruc]

I played quite a bit with vertex three coloring in the past and it has a surprisingly sharp phase transition. If you randomly generate graphs by including each possible edge with probability p, then the graph will have average degree p×n. Don't quote me on the exact numbers, but something like if the average degree is about 3, then the graph is usually hard to color. If it is only 2.9, then the graph is usually easy to color, if it is 3.1 then there is usually either no valid coloring at all or it is easy to find one. So of all the graphs with average degree from 0 to n, mostly only graphs with average degree in a narrow band around 3 are hard.