Связный неорграф без петель, имеющий

1. 
   Гамильтоновы графы. Постановка задачи коммивояжера.
   

Граф называется гамильтоновым, если в нем имеется простой цикл (гамильтонов цикл), содержащий каждую вершину этого графа. Простая цепь, содержащая все вершины графа, также называется гамильтоновой.

Пусть G – связный неорграф без петель, имеющий n≥3 вершин.
Достаточные условия существования гамильтоновых циклов:

1. 
   Если для любых двух различных несмежных вершин a и b графа G выполняется условие dega+degb≥n, то существует гамильтонов цикл.
   
2. 
   Если для любой вершины a графа G выполнено условие dega≥n/2, то существует гамильтонов цикл.
   

гамильтоновым циклом является такой цикл (замкнутый путь), который проходит через каждую вершину данного графа ровно по одному разу[2]; то есть простой цикл, в который входят все вершины графа.