Доказать, что в вершинах многогранника можно расставить натуральные числа так, что в каждых двух вершинах, соединённых ребром, стоят числа не взаимно простые, а в каждых двух вершинах, не соединённых ребром, взаимно простые.
Примечание: простых чисел бесконечно много.

   Решение

Тема:    [ Степень вершины ]

Сложность: 2 Классы: 6,7

Прислать комментарий

Условие

Докажите, что не существует графа без петель и кратных рёбер с пятью вершинами, степени которых равны 4, 4, 4, 4, 2.

Решение

Пусть степень каждой из четырёх вершин равна 4. Это значит, что каждая из них соединена со всеми остальными вершинами (в том числе и с пятой). Значит, степень пятой вершины также равна 4.

Источники и прецеденты использования