Изменения

Граф называется '''произвольно вычерчиваемым из вершины <tex>v</tex>''' (англ. '''Arbitrarily traceable graph'''), если любая цепь с началом в вершине <tex>v </tex> может быть продолжена до эйлеровой цепи графа <tex>G</tex>. Разумеется, если граф произвольно вычерчиваем из вершины <tex>v</tex>, то он является эйлеровым графом. }}

Пусть вершина <tex>v</tex> эйлерова графа <tex>G</tex> принадлежит любому циклу. Рассмотрим произвольную <tex>(''v, w'')-</tex> — цепь <tex>P</tex> и покажем, что её можно продолжить до эйлеровой цепи. Обозначим через <tex>G_1</tex> подграф графа <tex>G</tex>, полученный удалением из <tex>G</tex> всех рёбер цепи <tex>P</tex>. Если ''<tex>w=v''</tex>, то все вершины подграфа <tex>G_1</tex> имеют чётную степень, если же <tex>w≠vw\ne 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> существует полу-эйлерова <tex>(''v, w,v'')-</tex> — цепь <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>