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

Решение:

Это задача на графы. В данном случае телефоны — это вершины графа, а провода — это рёбра. Условие задачи означает, что мы ищем граф с 15 вершинами, в котором степень каждой вершины равна 3. Такой граф называется 3-регулярным графом.

Согласно лемме о рукопожатиях (сумма степеней всех вершин графа равна удвоенному числу рёбер), сумма степеней всех вершин должна быть чётным числом. В нашем случае сумма степеней равна \( 15 \times 3 = 45 \), что является нечётным числом. Следовательно, такой граф построить невозможно.

Ответ: Нельзя. Сумма степеней вершин графа должна быть чётной, а \( 15 \times 3 = 45 \) — нечётное число.