Изменения

Неодноэлементный [[Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов|эйлеров граф]] ''<tex>G'' </tex> является произвольно вычерчиваемым из вершины ''<tex>v'' </tex> тогда и только тогда, когда вершина ''<tex>v'' </tex> принадлежит любому циклу графа ''<tex>G''</tex>.<br>

Пусть вершина ''<tex>v'' </tex> эйлерова графа ''<tex>G'' </tex> принадлежит любому циклу. Рассмотрим произвольную (''v, w'')-цепь ''<tex>P'' </tex> и покажем, что её можно продолжить до эйлеровой цепи. Обозначим через <tex>G_1</tex> подграф графа ''<tex>G''</tex>, полученный удалением из ''<tex>G'' </tex> всех рёбер цепи ''<tex>P''</tex>. Если ''w=v'', то все вершины подграфа <tex>G_1</tex> имеют чётную степень, если же ''<tex>w≠v''</tex>, то <tex>G_1</tex> содержит в точности две вершины нечётной степени. Пусть <tex>H_0</tex> – компонента связности графа <tex>G_1</tex> , содержащая вершину ''<tex>v''</tex>. Ясно, что вершина ''<tex>w'' </tex> принадлежит <tex>H_0</tex> . Следовательно, <tex>H_0</tex> – полуэйлеров граф, и потому в <tex>H_0</tex> существует полу-эйлерова (''w,v'')-цепь ''<tex>Q''</tex>. Очевидно, что <tex>H_0</tex> содержит все рёбра графа <tex>G_1</tex>. Предположим, что <tex>G_1</tex> содержит неодноэлементную компоненту связности ''<tex>H''</tex>, отличную от <tex>H_0</tex> . Тогда ''<tex>H'' </tex> – эйлеров граф, и потому в ''<tex>H'' </tex> содержится цикл. Этот цикл не проходит через вершину ''<tex>v''</tex>, что невозможно. Следовательно, все компоненты связности подграфа <tex>G_1</tex>, отличные от <tex>H_0</tex>, одноэлементны.<br>Таким образом, цепь ''<tex>Q'' </tex> содержит все рёбра графа <tex>G_1</tex>. Отсюда вытекает, что объединение цепей ''<tex>P'' </tex> и ''<tex>Q'' </tex> – эйлерова цепь в графе ''<tex>G''</tex>, являющаяся продолжением цепи ''<tex>P''</tex>.<br>Обратно, пусть в графе ''<tex>G'' </tex> существует цикл ''<tex>C''</tex>, не содержащий вершину ''<tex>v''</tex>. Рассмотрим подграф <tex>G_1</tex>, полученный удалением из ''<tex>G'' </tex> всех ребер цикла ''С''<tex>C</tex>. Пусть ''<tex>H'' </tex> – компонента связности подграфа <tex>G_1</tex>, содержащая вершину ''<tex>v''</tex>. Легко понять, что ''<tex>H'' </tex> – эйлеров граф. Обозначим через ''<tex>P'' </tex> эйлерову цепь подграфа . Можно считать, что началом и концом цепи ''<tex>P'' </tex> является вершина ''<tex>v''</tex>. Поскольку ''<tex>v'' </tex> не принадлежит циклу ''<tex>C''</tex>, цепь ''<tex>P'' </tex> нельзя продолжить до эйлеровой цепи графа ''<tex>G''</tex>.