It is true under the convention that we color each contiguous region the same color, and each contiguous region can get any color. It is pretty clearly not true if you insist that non-contiguous regions must be colored the same, which is what happens with enclaves.

This latter case is covered by the more abstract version of vertex coloring general graphs, which started with the four color conjecture by Guthrie in the late 1800's, but continues to this day with things like register coloring in compilers, schedule coloring in timetabling, and with the knowledge that graph three (vertex) coloring is NP-Complete.

Why can't you color every enclave the same color - something different from the province they're inside of?

The traditional 4-color map rule only says that each neighboring region has a different color, not that the colors are meaningful.

In mapping, enclaves are usually colored the same as the "parent" country to which they belong. It's an additional restriction that's actually well catered for in the generic graph coloring context, as opposed to the "map" coloring of the original problem (which did not bother with the enclave issue).

I believe his claim is that one country has 4 disconnected regions. If you have that and can only use one graph node to represent all of the disconnected regions then the adjacency graph isn't necessarily planar.