Специальная математика. Соловьев А.Е. - 50 стр.

Если таким образом пройдены все ребра графа, то теорема доказана. Иначе выбирается
новая вершина, инцидентная непройденным ребрам (их четное число) и строится новый
цикл. И так до исчерпания непройденных ребер графа.
Таким образом, теорема доказана. А, следовательно, решена и задача о Кенигсбергских
мостах. Слово «решена» здесь используется в расширненном понимании, принятом в
обиходе у математиков, поскольку Эйлер на самом-то деле доказал, что задача не имеет
решения.

Следствие. Для того, чтобы в графе существовала Эйлерова цепь необходимо, чтобы в нем
было ровно две вершины с нечетной степенью, причем эта цепь начинается в одной из этих
вершин и заканчивается в другой.
Известная детская задача нарисовать, не отрывая карандаша, домик – лучшая иллюстрация к
этому следствию.




Элементарный цикл, проходящий через все вершины, называется гамильтоновым циклом,
а соответствующий граф – гамильтоновым графом.
Пример гамильнтонова графа




                                       — 50 —