9

Связность графов и маршруты Эйлеровы и гамильтоновы графы

Критерий эйлеровости и полуэйлеровости

Теорема. Связный граф имеет эйлеров путь тогда и только тогда, когда степени всех вершин четны.

Теорема. Связный граф имеет полуэйлеров путь тогда и только тогда, когда имеется только две вершины с нечетными степенями.