Графы. Задача о Кёнигсбергских мостах.

Обобщение решения задачи. Решая задачу в общем виде, Леонард Эйлер попутно доказал, что для любого графа число вершин с нечётным количеством рёбер чётно: «Вначале я отмечу, что все количества мостов», ведущих в области, «сложенные вместе, дают удвоенное число всех мостов. Причина состоит в том, что при таком подсчёте каждый мост считается дважды, с тем чтобы все мосты, ведущие в данную область, были учтены, ибо каждый мост ведёт в две области, которые он соединяет. 17. Из этого наблюдения вытекает, что сумма [чисел] всех мостов, ведущих в каждую область, есть чётное число, так как половина этой суммы есть в точности число мостов. Поэтому не может случиться так, чтобы среди чисел мостов, ведущих в любую область, в точности одно было нечётным; не может также случиться, чтобы нечётных чисел было три, пять и т. д. Следовательно, если числа мостов», ведущих в области, «суть нечётные числа, их сумма чётна». В конце статьи Леонард Эйлер записал общие выводы для любого графа вполне современным языком[25]: 20. Значит в каждом возможном случае следующее правило позволяет непосредственно и без труда выяснить, можно ли осуществить прогулку по всем мостам без повторений: Если имеется более двух областей, в которые ведет нечётное число мостов, можно заявить с уверенностью, что такая прогулка невозможна. Если, однако, имеются только две области, в которые ведёт нечётное число мостов, то прогулка осуществима при условии, что она начинается в одной из этих двух областей. Если, наконец, нет ни одной области, в которую ведёт нечётное число мостов, прогулка с требуемыми условиями осуществима, причём начинаться она может в любой области. Следовательно, с помощью этого правила поставленная задача может быть полностью решена. — Леонард Эйлер. Решение одной задачи, связанной с геометрией положения