На рисунке изображён граф. Какова наибольшая длина его простого цикла?

Назовём вершины: A — левая, B — верхняя левая, C — верхняя правая, D — средняя верхняя, E — правая, F — нижняя левая, G — нижняя правая.

Рёбра: AB, BC, BF, CF, CG, DG, DE, CE.

Вершина A имеет степень , поэтому ребро AB в цикл не входит.

Циклы графа:

• B–C–F–B, длина ;
• C–G–D–E–C, длина .

Эти два цикла имеют общую только вершину C. Простой цикл не повторяет вершины, поэтому объединить их в один нельзя. Наибольший простой цикл — C–G–D–E–C.

Используем те же вершины и рёбра: AB, BC, BF, CF, CG, DG, DE, CE.

В цикле вершины могут повторяться, а рёбра — нет. Поэтому можно пройти оба цикла подряд через общую вершину C:

Этот путь использует + = различных рёбер. Ребро AB добавить нельзя: A — висячая вершина, вернуться из неё по другому ребру невозможно.