Каковы основные принципы обхода графа одним росчерком пера?

Основные принципы обхода графа одним росчерком, сформулированные Леонардом Эйлером: nsportal.ru infourok.ru

1. Проверить связность графа. dzen.ru Если граф не связный (из любой вершины нельзя добраться до любой другой), то обвести его одним росчерком невозможно. dzen.ru
2. Посчитать степени всех вершин. dzen.ru Степень вершины — это количество рёбер, выходящих из неё. dzen.ru Если все вершины имеют чётную степень, то в графе есть эйлеров цикл, и можно начать с любой вершины и закончить в ней же. dzen.ru
3. Определить количество нечётных вершин. nsportal.ru Если ровно две вершины имеют нечётную степень, то в графе есть эйлеров путь, и нужно начать в одной из этих вершин и закончить в другой. dzen.ru Если больше двух вершин имеют нечётную степень, то обвести граф одним росчерком невозможно. dzen.ru
4. Указать начало и конец пути. nsportal.ru Если в графе есть эйлеров цикл (все вершины имеют чётную степень), то нужно закончить в той же вершине, с которой начали. dzen.ru Если в графе есть эйлеров путь (ровно две вершины имеют нечётную степень), и начали в одной из вершин с нечётной степенью, то нужно закончить в другой вершине с нечётной степенью. dzen.ru