Рассмотрим граф G на 2n вершинах (n > 1). а) Верно ли, что либо сам граф G либо его дополнение содержат гамильтонов цикл? б) Изменится ли ответ, если известно, что G — регулярный граф?

Дано:

• Граф $G$ на $2n$ вершинах, где $n > 1$.

Найти:

1. Верно ли, что либо сам граф $G$, либо его дополнение содержит гамильтонов цикл?
2. Изменится ли ответ, если известно, что $G$ — регулярный граф?

Решение:

а) Гамильтонов цикл в графе или его дополнении

Для начала, напомним, что гамильтонов цикл — это цикл в графе, который проходит через каждую вершину ровно один раз и возвращается в начальную.

Согласно теореме, известной как теорема о гамильтоновом цикле для графов с достаточной связностью, если граф $G$ имеет достаточно много рёбер, то он содержит гамильтонов цикл...