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

Tất cả các bản đồ ở trên đều có thể được tô với chỉ 4 màu khác nhau, và cũng không khó để tưởng tượng được rằng các bản đồ phức tạp khác có thể cần nhiều màu hơn. Thực tế một số bản đồ cần ít nhất bốn màu, khi bản đồ có 4 vùng kết nối với nhau.

Tương tự như trước, chúng ta có thể chuyển đổi bản đồ với vùng miền khác nhau thành một đồ thị phẳng: với mỗi vùng trở thành một đỉnhmột cạnhmột mặt, và các vùng có chung biên giớicó cùng một màu kết nối với nhau bởi một cạnh:

Bây giờ chúng ta muốn tô màu các đỉnh của đồ thị, và hai đỉnh phải có màu khác nhau nếu chúng được kết nối bằng một cạnh.