211
правок
Изменения
Нет описания правки
{{Теорема
|statement=
Неодноэлементный [[Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов|эйлеров граф ]] ''G'' является произвольно вычерчиваемым из вершины ''v'' тогда и только тогда, когда вершина ''v'' принадлежит любому циклу графа ''G''.<br>
|proof=
Пусть вершина ''v'' эйлерова графа ''G'' принадлежит любому циклу. Рассмотрим произвольную (''v, w'')-цепь ''P'' и покажем, что её можно продолжить до эйлеровой цепи. Обозначим через <math>G_1</math> подграф графа ''G'', полученный удалением из ''G'' всех рёбер цепи ''P''. Если ''w=v'', то все вершины подграфа <math>G_1</math> имеют чётную степень, если же ''w≠v'', то <math>G_1</math> содержит в точности две вершины нечётной степени. Пусть <math>H_0</math> – компонента связности графа <math>G_1</math> , содержащая вершину ''v''. Ясно, что вершина ''w'' принадлежит <math>H_0</math> . Следовательно, <math>H_0</math> – полуэйлеров граф, и потому в <math>H_0</math> существует полуэйлерова (''w,v'')-цепь ''Q''. Нетрудно понять, что <math>H_0</math> содержит все рёбра графа <math>G_1</math>. В самом деле, предположим, что <math>G_1</math> содержит неодноэлементную компоненту связности ''H'', отличную от <math>H_0</math> . Тогда ''H'' – эйлеров граф, и потому в ''H'' содержится цикл. Этот цикл, очевидно, не проходит через вершину ''v'', что невозможно. Следовательно, все компоненты связности подграфа <math>G_1</math>, отличные от <math>H_0</math>, одноэлементны.<br>
