Định lý bốn màu phát biểu rằng bất kỳ bản đồ nào vẽ trên một mặt phẳng đều có thể được tô bằng nhiều nhất bốn màu sao cho không có hai vùng nào có chung một đường biên lại cùng màu. Hai vùng chỉ chạm nhau tại một điểm không được tính là “có chung biên”. Đây là cách diễn đạt theo bản đồ của một kết quả về đồ thị phẳng.
Các vùng 1, 2, 3, 4 mỗi vùng đều giáp với nhiều vùng khác. Vùng (4) bên trái và vùng (4) bên phải không có chung biên nên chúng có thể dùng cùng một màu. Ví dụ này cần đúng 4 màu.
Francis Guthrie đã đưa ra phỏng đoán vào năm 1852 khi tô màu một bản đồ các hạt ở Anh. Ông nhận thấy bốn màu dường như luôn đủ nhưng không thể chứng minh. Bài toán nhanh chóng trở thành một trong những câu hỏi nổi tiếng nhất của toán học tổ hợp.
Định lý bốn màu mất 124 năm từ lúc được phỏng đoán đến khi được chứng minh. Chứng minh năm 1976 là định lý lớn đầu tiên được kiểm chứng bằng máy tính.
Chứng minh năm 1976 của Kenneth Appel và Wolfgang Haken là định lý lớn đầu tiên được máy tính chứng minh. Nó rút gọn mọi bản đồ có thể có về 1.936 cấu hình và để máy tính kiểm tra rằng mỗi cấu hình đều có thể rút tiếp. Điều này đã gây tranh luận triết học về việc liệu một chứng minh quá dài để con người kiểm tra từng bước có còn là chứng minh hay không.
Năm vùng ngoài (một số lẻ) buộc vòng phải dùng 3 màu: không thể tô 2 màu cho một chu trình 5 cạnh. Vùng trung tâm kề với cả năm vùng, chạm tới cả 3 màu đó, nên nó cần màu thứ tư.
Mọi bản đồ vẽ trên một mặt phẳng đều có thể được tô bằng nhiều nhất bốn màu sao cho không có hai vùng có chung biên nào cùng màu. Francis Guthrie đã phỏng đoán điều này năm 1852. Appel và Haken đã chứng minh nó năm 1976 bằng một chứng minh có hỗ trợ của máy tính, khiến đây trở thành định lý lớn đầu tiên được xác minh bằng máy tính.