Эйлеровы графы

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

Граф называется Эйлеровым, если он связен и в нем имеется цикл, проходящий по одному разу через каждое ребро, этот цикл тоже называется Эйлеровым циклом.

Замечание: это определение применяется так же к графам с кратными ребрами.

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

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

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

Где может остановиться этот маршрут? Маршрут может остановиться только в V0. Поскольку ребра не повторяются, то маршрут будет циклическим. Если этот цикл содержит все ребра данного графа, то он Эйлеров и теорема доказана, а если содержит не все ребра, то он не будет Эйлеров.

д/з