The Four Color Theorem states that any planar graph can be properly vertex-colored using at most 4 colors, and this bound is tight (some planar graphs, like K4, genuinely require 4).