Để giải bài toán này, ta có thể sử dụng nguyên lý cơ bản của lý thuyết đồ thị. Đầu tiên, chúng ta chia bảng thành 2 trường hợp:

1. Nếu có một chu trình chứa số lượng ô vuông là số chẵn (chẵn số ô vuông), thì ta có thể tô cùng màu cho tất cả các ô vuông trong chu trình đó.

2. Nếu không có chu trình nào chứa số lượng ô vuông là số chẵn, thì ta có thể tô cùng màu cho một số lẻ các ô vuông trên bảng.

Với bảng 9 ô vuông, không thể có chu trình chứa số lượng ô vuông là số chẵn (vì số lẻ ô vuông), vì vậy ta có thể tô cùng màu cho ít nhất 5 ô vuông.