На плоскости дано 100 окружностей, составляющих связную (то есть не распадающуюся на части) фигуру.
Докажите, что эту фигуру можно нарисовать, не отрывая карандаша от бумаги и не проводя дважды одну и ту же линию.

   Решение

Темы:    [ Обход графов ] [ Четность и нечетность ]

Сложность: 3 Классы: 8,9

Прислать комментарий

Условие

На плоскости дано 100 окружностей, составляющих связную (то есть не распадающуюся на части) фигуру.
Докажите, что эту фигуру можно нарисовать, не отрывая карандаша от бумаги и не проводя дважды одну и ту же линию.

Решение

Граф связен, степени всех его вершин чётны (см. задачу 30806).

Источники и прецеденты использования