Эйлеровы графы. Гамильтоновы графы

математик, механик и физик .

Задача «кругосветного путешествия» по додекаэдру, узловые вершины которого символизировали крупнейшие города Земли

и
 m - минимальная степень его вершин. Если n≥3  и m ≥n/2, то  G - гамильтонов граф.

Теорема Оре. Пусть  G - неориентированный граф порядка n. Если  n≥3  и  deg(u)+deg(v) ≥ n для любых двух различных несмежных вершин u  и v , то G - гамильтонов граф.

Если неориентированный граф G содержит гамильтонов цикл, тогда в нём не существует ни одной вершины u со степенью u < 2. 

Необходимое условие гамильтоновости графа