Bài toán bốn màu: Tô bản đồ nào cũng chỉ cần 4 màu

Xếp lịch thi sao cho hai môn có chung học sinh không thi cùng giờ, chia tần số cho các trạm phát sóng đặt gần nhau, tô bản đồ sao cho hai nước láng giềng không trùng màu: cả ba việc này là cùng một bài toán. Giới toán học mất 124 năm mới chứng minh được bài toán tô bản đồ, và phải nhờ tới máy tính.

Năm 1852, khi tô bản đồ các hạt của nước Anh, Francis Guthrie nhận thấy mình chỉ cần 4 màu. Ông tự hỏi: có phải bản đồ nào cũng vậy không? Luật tô: hai vùng chung một đoạn biên giới phải khác màu. Hai vùng chỉ chạm nhau ở một điểm thì được phép cùng màu.

Từ khóa: chứng minh, tô màu bản đồ, lý thuyết đồ thị, lịch sử toán học