TÔ MÀU HÌNH BÊN GỒM 6 ĐỈNH A, B, C, D, E, F VÀ CÁCCẠNH NỐI MỘT SỐ ĐỈNH...

Bài 101: Tô màu Hình bên gồm 6 đỉnh A, B, C, D, E, F và cáccạnh nối một số đỉnh với nhau. Ta tô màu các đỉnh sao cho haiđỉnh được nối bởi một cạnh phải được tô bởi hai màu khác nhau.Hỏi phải cần ít nhất là bao nhiêu màu để làm việc đó? Bài giải: Tất cả các đỉnh A, B, C, D, E đều nối với đỉnh F nên đỉnh F phải tômàu khác với các đỉnh còn lại. Với 5 đỉnh còn lại thì A và C tô cùngmột màu. B và D tô cùng một màu, E tô riêng một màu, như vậy cần ítnhất 3 màu để tô 5 đỉnh sao cho 2 đỉnh được nối bởi một cạnh được tôbởi 2 màu khác nhau. Vậy cần ít nhất 4 màu để tô 6 đỉnh của hìnhtheo yêu cầu của đề bài.