Question

Вгороде маленьком 15 телефонов . некоторые соединены ( каждый провод соединяет ровно два телефона ) . в город пробрался хулиган и разрезал каждый провод пополам . и теперь от 5 телефонов отходит по 6 половинок проводов , а от остальных 10 телефонов - по 3 половинки . сколько всего проводов разрезал хулиган?

Answer 1

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