Сколько из изображенных на рисунке графов можно нарисовать, не отрывая карандаша от бумаги?

Граф 1 (четырёхконечная звезда в круге):

• Вершины звезды (4 вершины): степень 3
• Пересечения линий звезды (4 вершины): степень 4
• Вершины, где звезда касается круга (4 вершины): степень 2

Всего 4 вершины имеют нечетную степень (3), следовательно, этот граф нельзя нарисовать, не отрывая карандаша.

Граф 2 (две соединенные фигуры, похожие на ромб):

• Левая вершина (степень 2)
• Правая вершина (степень 2)
• Верхняя центральная (степень 4)
• Нижняя центральная (степень 4)
• Верхние боковые (степень 2)
• Нижние боковые (степень 2)

Этот граф можно нарисовать не отрывая карандаша, так как все вершины имеют четную степень.

Граф 3 (пятиконечная звезда):

• Все 5 вершин имеют степень 2

Этот граф можно нарисовать не отрывая карандаша, так как все вершины имеют четную степень.

Граф 4 (окружность с линией посередине):

• Все точки, кроме пересечений, имеют степень 2.
• Две вершины на окружности (степень 3)

Имеет 2 вершины нечетной степени, поэтому является полуэйлеровым и его можно нарисовать одним росчерком.

Итого, можно нарисовать 3 графа, не отрывая карандаша.

Ответ: 3