bài toán bản đồ bốn màu

Bài toán bản đồ bốn màu đặt vấn đề: cần ít nhất bao nhiêu màu để tô màu các quốc gia hoặc các khu vực lân cận có chung biên giới. Đây là bài toán khó nổi tiếng đã hấp dẫn nhiều nhà toán học xuất sắc.

Bài toán bản đồ bốn màu chính thức đặt ra vào năm 1852 do một học sinh của Trường đại học Luânđôn hỏi thầy giáo là giáo sư toán học Môngan. Ông không giải được và đã thảo luận với các nhà toán học khác nhưng cũng không giải quyết được, do đó đã trở thành bài toán khó và lưu truyền cho đời sau.

Sau đó, đã có nhà toán học cho rằng: với bất kì một tấm bản đồ nào, chỉ cần dùng 4 màu là đủ. Đến tháng 9 năn 1976 “Thông báo của hội toán học Hoa Kì” đã đưa ra một tuyên bố làm chấn động giới toán học toàn thế giới: hai giáo sư của Trường đại học Ilinôi là Abel và Hagan đã dùng máy tính điện tử chứng minh là bài toán bản đồ bốn màu là chính xác. Họ đã xem xét bài toán bốn màu cho 2000 bản đồ đặc thù và đã dùng 1200 giờ máy tính để chứng minh bài toán trên.