Изменения
Нет описания правки
# Доказать или опровегнуть, что если $G$ содержит порожденный тета-подграф (две вершины, соединенные тремя путями), то $G$ не гамильтонов.
# Обозначим как $G^3$ граф, в котором две вершины соединены, если они соединены в $G$ путем длины не более 3. Докажите, что если $G$ связен, то $G^3$ гамильтонов.
# Граф называется произвольно гамильтоновым, если следующая процедура всегда приводит к гамильтонову циклу: начиная с произвольной вершины $u$, переходим каждый раз по любому исходящему из текущей вершины ребру, другой конец которого мы ранее не посещали, либо обратно в вершину $u$, если непосещенных соседей нет. Опишите все произвольно гамильтоновы графы.
# Теорема "Антихватала". Докажите, что если не выполнено условие теоремы Хватала, то найдется граф с такой степенной последовательностью, не содержащий гамильтонова цикла.
# Докажите, что если сумма степеней любых двух несмежных вершин графа $G$ не меньше $n+1$, то любые две различные вершины $G$ можно соединить гамильтоновым путем.
# Докажите, что для любого $k$ существует негамильтонов граф с $\kappa(G)=k$.гамильтоновым путем.
# Обозначим как $G^2$ граф, в котором две вершины соединены, если они соединены в $G$ путем длины не более 2. Докажите, что если $G$ вершинно двусвязен, то $G^2$ гамильтонов.
</wikitex>
