Довільно викреслювані із заданої вершини графи

[math]\Rightarrow[/math] Нехай [math]G[/math] [math]\exists[/math] цикл [math]C, v \notin C[/math] . Розглянемо [math]G_1 = G/C[/math] (тут і далі це означає видалення тільки ребер, не чіпаючи вершини). При видаленні циклу всі ступеня вершин залишилися парними, тому що кожна вершина містить парну кількість ребер циклу, а отже [math]G_1[/math] — ейлерів. Тоді [math]G_1[/math] [math]\exists[/math] ейлерів цикл. Якщо почати обхід по ейлерову циклу з [math] v [/ math], то і закінчиться він в [ math] v [/ math]. Якщо тепер повернути цикл [math]C[/math] , ми ніяк не зможемо його обійти, оскільки з вершини [math]v[/math] більше немає відвіданих ребер [math]\Rightarrow[/math] [math] G[/math] не вільно викреслюється з [math]v[/math].

[math]\Leftarrow[/math] Нехай дано ейлерів граф [math]G[/math] , вершина [math]v[/math] належить всім його циклам. Розглянемо довільний шлях [math] P = v \ leadsto w [/ math]. Нехай [math]G_1 = G/P[/math]. Можливі 2 випадки:

Якщо [math]v = w[/math] , то [math]P[/math] — цикл, значить ступеня всіх вершин у [math]G_1[/math] залишилися парними [math]\Rightarrow[/math] [math ] G_1 [/ math] - ейлерів.
Якщо [math]v \neq w[/math] , то оскільки [math]G[/math] ейлерів граф [math]\exists[/math] ейлерів шлях [math]w \leadsto v \in G_1[/math ].

Покажемо, що у обох випадках ейлерів обхід пройде по всіх ребрах [math]G_1[/math] .

[math]G[/math] [math]\exists[/math] єдина компонента зв'язності, що містить ребра. При видаленні [math]P[/math] їхня кількість не могла збільшитися, інакше має бути цикл, що не містить [math]v[/math] (дивися малюнок). Значить [math]G_1[/math] [math]\exists[/math] єдина компонента зв'язності містить ребра,причому [math]G_1[/math] або напівейлерів, або ейлерів [math]\Rightarrow[/math] в [math]G_1[/math] [math]\exists[/math] ейлеровий ланцюг [math]Q = w \ leadsto v[/math] [math]\Rightarrow[/math] [math]P+Q[/math] ейлерів цикл у графі [math]G[/math] .

Спираючись на теорему, опишемо будову всіх графів, що довільно викреслюються з вершини [math]v[/math] . Візьмемо довільний ліс [math]H[/math], що не містить вершини [math]v[/math]. Кожну вершину непарного ступеня з'єднаємо деяким непарним числом кратних ребер з [math]v[/math] , а кожну вершину парного ступеня [math]-[/math] парним числом кратних ребер з [math]v[/math] (не виключаючи [ math]0[/math] ), причому кожну ізольовану вершину обов'язково з'єднаємо з [math]v[/math]. Отриманий граф [math]G[/math] :

зв'язаний,
має тільки вершини парного ступеня,
є довільно викреслюваним з [math]v[/math] як ейлерів граф, у якого [math]v[/math] належить всім циклам.

Тепер доведемо, чому таким чином можна отримати всі графи, які довільно викреслюються з вершини [math]v[/math]. Нехай якийсь такий граф не можна отримати за методом описаним вище. Тоді приберемо всі ребра з вершини [math] v [/ math] і подивимося на граф, що залишився. Він не є лісом, інакше ми могли б одержати цей граф нашим методом. Але якщо він не є лісом, то в ньому є хоча б один цикл, який не містить [math] v [/ math]. А за теоремою про довільно викреслювані з вершини графи такого бути не може. Отже, наше припущення помилкове.