Цикл и цепь Гамильтона. Граф Гамильтона и его свойства

Цикл Гамильтона (ЦГ) – замкнутая цепь, содержащая все вершины графа. Если граф содержит хотя бы 1 ЦГ, то и граф – Гамильтона (ГГ).

Если граф не содержит ни одного ЦГ, но для его составления не хватает одного единственного ребра, то такой граф – полугамильтоновый, а цепь в которую добавляется ребро – цепь Гамильтона.

Теорема Дирака. Связный граф – ГГ при условии где n – количество вершин.