One way to convince you would be to show you how to color the map with three colors, but that would ruin the puzzle.

Can you think of a way for me to convince you without revealing the solution?