Four color theorem
The simplest counterexamples generally try to create one region which touches all the others. This forces the remaining regions to be colored with only three colors. Because the four color theorem is true, this is always possible; however, because the person drawing the map is focused on the one large region, they do not notice that the remaining regions can in fact be colored with three colors.