В городке Махоньком 15 телефонов. Можно ли их соединить проводами так,

Ответ: это невозможно.
РЕШЕНИЕ. Представим, что это вероятно. Осмотрим тогда граф, верхушки которого соответствуют телефонам, а ребра - объединяющим их проводам. В этом графе 15 вершин, степень каждой из которых одинакова 5. Подсчитаем количество ребер в этом графе. Для этого поначалу просуммируем степени всех его вершин. Светло, что при таком подсчете каждое ребро учтено два раза (оно ведь объединяет две верхушки!). Потому число ребер графа должно быть одинаково 15 5/2. Но это число нецелое! Следовательно, такого графа не существует, а означает, и соединить телефоны требуемым образом невероятно.

Допустим, что такое соединение телефонов вероятно. Тогда представим для себя граф, в котором вершины обозначают телефоны, а ребра провода, их объединяющие. Подсчитаем, сколько всего получится проводов. К каждому телефону подключено ровно 5 проводов, т.е. ступень каждой верхушки нашего графа 5.Чтоб отыскать число проводов, надобно просуммировать степени всех вершин графа и приобретенный итог разделить на 2 (т.к. каждый провод имеет два конца, то при суммировании степеней каждый провод будет взят 2 раза). Но тогда количество проводов получится различным nbsp;15*5/2 =37,5 . Но это число не целое. Означает наше предположение о том, что можно соединить каждый телефон ровно с пятью иными, оказалось неправильным.
Ответ. Соединить телефоны таким образом невероятно.