4. Можно ли изображённый на рисунке граф нарисовать, не отрывая карандаш от бумаги и не проводя ни одно ребро дважды? Если да, укажите такой путь (перечислите вершины). Если это невозможно, объясните почему.

Решение:

Данный граф можно нарисовать, не отрывая карандаш от бумаги и не проводя ни одно ребро дважды, если количество вершин с нечётной степенью равно 0 или 2.

Степень вершины — это количество рёбер, выходящих из неё.

В данном графе:

• Степень вершины A: 2 (ребра AB, AF)
• Степень вершины B: 2 (ребра BA, BG)
• Степень вершины C: 2 (ребра CD, CH)
• Степень вершины D: 2 (ребра DC, DE)
• Степень вершины E: 3 (ребра ED, EK, EF)
• Степень вершины F: 3 (ребра FA, FK, FE)
• Степень вершины G: 2 (ребра GB, GK)
• Степень вершины H: 2 (ребра HC, HK)
• Степень вершины K: 3 (ребра KE, KG, KH)

Мы видим, что вершины E, F, K имеют нечётную степень (3). Так как таких вершин 3, а не 0 или 2, то нарисовать данный граф, не отрывая карандаш и не проводя ребро дважды, невозможно.

Ответ: Невозможно. В графе 3 вершины (E, F, K) имеют нечётную степень (3), а для возможности такого рисования их должно быть 0 или 2.