Раскраска в графах

[kati]

1) Каждые две из 15 вершин графа соединены ребром. Можно ли все ребра графа покрасить в один из 14 цветов так, чтобы из любой вершины выходили ребра всех 14 цветов?
2) Все страны, расположенные на острове имеют форму треугольников, причем любые две соседние страны имеют общую сторону. Доказать, что карта острова 3-раскрашиваема.
3) На острове расположено несколько стран. Можно ли разбить некоторые из этих стран на меньшие так, чтобы все старые границы сохранились, а получившуюся карту можно было раскрасить в 2 цвета?

[Хорхе]

1. Сколько ребер каждого цвета получится?
3. Что можно сказать о 2-раскрашиваемом графе?

[kati]

1) Получится 14 ребер.
2) Карта 2-раскрашиваема тогда и только тогда,когда граф эйлеров.

[ИСН]

1) Тут надо начинать издалека. Сколько всего рёбер в графе? Не одного цвета, а вообще всего?