Домашка по графам

2. На одну из вершин дерева T ставится фишка. Далее повторяется следующая процедура: фишки
снимаются со всех вершин, где они стояли на предыдущем этапе, и фишки ставятся на все вершины,
смежные хотя бы с одной вершиной, на которой стояла фишка на предыдущем этапе. Докажите, что
после любого количества повторений этой процедуры фишки не будут стоять на всех вершинах дерева.
3. В простом неориентированном графе 17 вершин. Они расставлены по кругу так, что каждое из 34
рёбер графа соединяет пару соседних в расстановке вершин или пару вершин, между которыми есть
ровно одна другая вершина. Можно ли вершины этого графа правильно раскрасить в 3 цвета?
5. В простом неориентированном графе на 30 вершинах (необязательно двудольном) между любыми
тремя вершинами есть хотя бы два ребра. Докажите, что в графе есть совершенное паросочетание (из
15 рёбер).
6. На ОП «Уникумы» есть 10 курсов. На очередной семестр каждому студенту этой ОП назначено
множество из 4 курсов, причём для разных студентов ...