Are there 3-colorable maps that can never be colored?
Every formal statement can be translated into a map in a way that preserves truth. If a statement is true, its map will be 3-colorable. If not, it isn't 3-colorable https://youtu.be/5ovdoxnfFVc?t=1721

Every formal statement in propositional logic can be translated to a map 3-coloring instance. The video is being very sloppy with calling this 'every mathematical statement', as there's many mathematical statements that aren't captured in propositional logic.
Propositional logic is decidable (it's equivalent to the SAT problem).