Произвольно вычерчиваемые из заданной вершины графы

Определение:

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

Теорема:

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

Доказательство:

[math]\triangleright[/math]

Пусть вершина 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], одноэлементны. Таким образом, цепь Q содержит все рёбра графа [math]G_1[/math]. Отсюда вытекает, что объединение цепей P и Q – эйлерова цепь в графе G, являющаяся продолжением цепи P. Обратно, пусть в графе G существует цикл C, не содержащий вершину v. Рассмотрим подграф [math]G_1[/math], полученный удалением из G всех ребер цикла С. Пусть H – компонента связности подграфа [math]G_1[/math], содержащая вершину v. Легко понять, что H – эйлеров граф. Обозначим через P эйлерову цепь подграфа . Можно считать, что началом и концом цепи P является вершина v. Поскольку v не принадлежит циклу C, цепь P нельзя продолжить до эйлеровой цепи графа G.

[math]\triangleleft[/math]

Источники:
Асанов М., Баранский В., Расин В. - Дискретная математика: Графы, матроиды, алгоритмы — Ижевск: ННЦ "Регулярная и хаотическая динамика", 2001, 288 стр.