Ответ:

Решение:

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

Рассмотрим степени вершин на рисунке:

  • Вершина A: степень 2 (ребра AF, AB)
  • Вершина F: степень 2 (ребра FA, FK)
  • Вершина K: степень 4 (ребра KF, KE, KG, KH)
  • Вершина E: степень 2 (ребра EK, ED)
  • Вершина D: степень 1 (ребро DE)
  • Вершина G: степень 2 (ребра KG, GB)
  • Вершина B: степень 1 (ребро BG)
  • Вершина C: степень 1 (ребро CH)
  • Вершина H: степень 2 (ребра HK, HC)

Вершины с нечетной степенью: D (1), B (1), C (1). Всего 3 вершины с нечетной степенью.

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

Ответ: Нельзя, так как в графе 3 вершины имеют нечетную степень (D, B, C).