Применение теоремы Эйлера к некоторым задачам Б. В. Бекламов
    В этой статье мы предлагаем читателям несколько задач, в решении которых центральную роль играет теорема Эйлера. Уделяя основное внимание задачам, мы не доказываем здесь эту теорему, а приводим лишь её формулировку. Доказательство теоремы Эйлера, как и более общие формулировки этой теоремы, можно найти в книгах "Что такое математика?" Куранта и Роббинса и "Наглядная геометрия" Гильберта и Кон-Фоссена.
    Прежде чем формулировать теорему Эйлера, договоримся, что линию с концами в двух данных точках мы будем называть дугой, соединяющей эти точки, в том случае, если эту линию можно пройти, не побывав ни в одной из её точек дважды.
    Теорема Эйлера. Пусть на плоскости задано m точек и n попарно непересекающихся дуг, каждая из которых соединяет какие-либо две данные точки и не проходит через остальные m-2 точки, и пусть эти дуги делят плоскость на l областей. Если из каждой данной точки в любую из остальных можно попасть, двигаясь по этим дугам, то
    m - n + l = 2.
    В случае, изображенном на рисунке1, все условия теоремы Эйлера выполнены, m=12, n=18, l=8 и m-n+l=2. На рисунках2 и 3 изображены случаи, когда условия этой теоремы не выполняются. Так, на рисунке2 из точки A1 нельзя попасть в точку A5 и m-n+l=3?2, а на рисунке3 линия, соединяющая точки A1 и A2, является самопересекающейся и опять m-n+l=3?2.
    
    Рис. 1.
    Рис. 2.
    Рис. 3.
    В некоторых задачах совокупность, состоящую из нескольких точек и соединяющих их попарно непересекающихся дуг, мы называем картой; при этом точки из этой совокупности мы называем вершинами, а области, на которые дуги делят плоскость, - странами.
    Теперь мы можем перейти к решению задач.
    Задача1. Можно ли десять городов соединить между собой непересекающимися дорогами так, чтобы из каждого города выходило пять дорог, ведущих в пять других городов?
    Решение. Предположим, что города можно соединить между собой дорогами так, как указано в задаче. В таком случае, если какие-то два города окажутся не соединенными дорогой непосредственно, то найдётся третий город, который уже будет непосредственно соединён с каждым из них. Изобразив на плоскости города точками, а дороги - дугами, получим, что любые две точки соединены цепочкой дуг. Так как в каждой точке сходятся пять дуг, то общее число дуг равно 1/2·5·10 = 25. Согласно теореме Эйлера эти дуги делят плоскость на 2 + 25 - 10 = 17 областей. Каждая из этих семнадцати областей ограничена по крайней мере тремя дугами, так как в противном случае нашлись бы два города, непосредственно соединённые по крайней мере двумя дорогами, а это противоречит условию задачи. Следовательно, число дуг не меньше 1/2·3·17 = 25,5. Таким образом, исходное предположение приводит нас к противоречию, и города нельзя соединить между собой так, как это требуется в задаче.
    Задача2. Три поссорившихся соседа имеют три общих колодца. Можно ли провести непересекающиеся дорожки от каждого дома к каждому колодцу?
    Решение. Предположим, что это сделать можно.
    Изобразим дома синими, а колодцы - чёрными точками и каждую синюю точку соединим дугой с каждой чёрной точкой так, чтобы девять полученных дуг попарно не пересекались. ............