Đồ thị và Mạng lướiMaps

Năm 1852, một sinh viên thực vật học Francis Guthrie phải tô màu các vùng của nước Anh. Ông quan sát được rằng hầu như chỉ cần 4 màu là đủ với bất kỳ bản đồ nào Ông thử, nhưng Ông tìm được minh chứng rằng quy tắc 4 màu này áp dụng được cho tất cả các bản đồ. Điều này thực ra là một bài toán cực kỳ khó, được biết đến với cái tên định lý bốn màu.

Trong suốt 100 năm sau đó, rất nhiều nhà toán học tìm cách công bố các chứng minh khác nhau cho định lý này, để rồi sau đó phát hiện ra nhiều lỗi. Trong số đó có những cách chứng minh có vẻ hết sức thuyết phục khiến phải mất hơn 10 năm mới phát hiện ra lỗi của nó.

Trong một thời gian dài, nhiều nhà toán học không tìm được cách chứng minh chỉ cần dùng 4 màu là đủ hoặc đưa ra các bản đồ cần dùng hơn 4 màu.