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

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

Определение 3. Граф, обладающий гамильтоновым циклом, называется гамильтоновым графом.

Теорема 14. Граф с m вершинами имеет гамильтонов цикл, если для любой его вершины A_i степень (A_i) ³ m/2.