Доказательство. База индукции: цикл существует

База индукции: цикл существует.

Предположим что граф имеющий менее вершин содержит эйлеров цикл.

Рассмотрим связный граф с вершинами, степени которых четны.

Пусть и — вершины графа. Поскольку граф связный, то существует путь из в . Степень — чётная, значит существует неиспользованное ребро, по которому можно продолжить путь из . Так как граф конечный, то путь, в конце концов, должен вернуться в , следовательно мы получим замкнутый путь (цикл). Назовем этот цикл . Будем продолжать строить через таким же образом, до тех пор, пока мы в очередной раз не сможем выйти из вершины , то есть будет покрывать все ребра, инцидентные . Если является эйлеровым циклом для , тогда доказательство закончено. Если нет, то пусть — подграф графа , полученный удалением всех рёбер, принадлежащих . Поскольку содержит чётное число рёбер, инцидентных каждой вершине, то каждая вершина подграфа имеет чётную степень. А так как покрывает все ребра, инцидентные , то граф будет состоять из нескольких компонент связности.

Рассмотрим какую-либо компоненту связности . Поскольку рассматриваемая компонента связности имеет менее, чем вершин, а у каждой вершины графа чётная степень, то у каждой компоненты связности существует эйлеров цикл. Пусть для рассматриваемой компоненты связности это цикл . У и имеется общая вершина , так как cвязен. Теперь можно обойти эйлеров цикл, начиная его в вершине , обойти , вернуться в , затем пройти и вернуться в . Если новый эйлеров цикл не является эйлеровым для , продолжаем использовать этот процесс, расширяя наш эйлеров цикл, пока, в конце концов, не получим эйлеров цикл для .

Поиск по сайту: