1. В городе Маленьком 15 телефонов. Можно ли их соединить проводами так, чтобы каждый телефон был соединен ровно с пятью другими?

Обоснование:

В данном случае мы имеем дело с графом, где телефоны — это вершины, а провода — это рёбра. Условие задачи требует, чтобы степень каждой вершины была равна 5 (каждый телефон соединен ровно с пятью другими).

По лемме о рукопожатиях (или теореме о сумме степеней вершин), сумма степеней всех вершин в любом графе равна удвоенному числу рёбер. То есть, \[ \sum_{i=1}^{n} deg(v_i) = 2|E| ]

В нашем случае, у нас 15 вершин (телефонов), и степень каждой вершины равна 5. Следовательно, сумма степеней всех вершин будет: \[ 15 × 5 = 75 ]

Согласно лемме о рукопожатиях, эта сумма должна быть чётным числом (удвоенное число рёбер). Однако, 75 — это нечётное число.

Вывод: Невозможно соединить 15 телефонов таким образом, чтобы каждый был соединен ровно с пятью другими, потому что сумма степеней вершин (15 × 5 = 75) оказалась нечётной, что противоречит лемме о рукопожатиях.

Ответ: Нет