Một mặt phẳng được chia bởi nhiều đường. Chứng minh rằng có thể tô màu các vùng được tạo thành chỉ bằng hai màu sao cho không có hai vùng liền kề nào có cùng màu.

Giải thích các bước giải:

1. Để chứng minh rằng có thể tô màu các vùng được tạo thành chỉ bằng hai màu sao cho không có hai vùng liền kề nào có cùng màu, ta sử dụng phương pháp chứng minh bằng quy nạp (induction).

   Giả sử mặt phẳng ban đầu được chia bởi nhiều đường tạo thành các vùng. Ta xét trường hợp đơn giản nhất là khi không có đường nào chia mặt phẳng, tức là chỉ có một vùng duy nhất. Trong trường hợp này, ta có thể tô màu vùng đó bằng bất kỳ màu nào.

   Giả sử đúng với mọi trường hợp có ít hơn n đường chia mặt phẳng, ta chứng minh rằng đối với trường hợp có n đường chia mặt phẳng, ta vẫn có thể tô màu các vùng được tạo thành chỉ bằng hai màu sao cho không có hai vùng liền kề nào có cùng màu.

   Giả sử ta đã tô màu được các vùng của mặt phẳng với n-1 đường chia mặt phẳng sao cho không có hai vùng liền kề nào có cùng màu. Khi ta thêm một đường chia mặt phẳng mới, nó sẽ tạo ra hai vùng mới. Ta có thể tô màu hai vùng này bằng hai màu khác nhau. Bởi vì không có hai vùng liền kề nào có cùng màu trước khi thêm đường mới, việc thêm đường mới chỉ tác động đến hai vùng gần đường mới và không làm thay đổi màu của các vùng khác.

   Vậy, ta đã chứng minh được rằng có thể tô màu các vùng được tạo thành chỉ bằng hai màu sao cho không có hai vùng liền kề nào có cùng màu.