Граф и клетчатая плоскость.

[Temur2000]

Клетчатая плоскость раскрашена десятью красками так, что соседние (т. е. имеющие общую сторону) клетки покрашены в разные цвета, причём все десять красок использованы. Две краски называются соседними, если ими покрашены какие-то две соседние клетки. Каково минимально возможное число пар соседних красок?
Задача уже выкладывалась, но ни подсказки, ни решения не было. Знаю должно быть 9, но как доказать что меньше не может быть?

[ИСН]

Элементарно: нарисуем граф с десятью вершинами. Вершины - это цвета, а связаны те из них, для которых есть соседние клетки этих цветов. Ну дак граф-то связный!