Ответ:

Решение:

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

Основное условие существования эйлерова цикла в связном графе: все вершины должны иметь чётную степень.

Рассмотрим рисунки:

  • Граф 1: Вершины имеют степени: 2, 2, 2, 2. Все степени чётные. Граф связный. Это эйлеров граф.
  • Граф 2: Вершины имеют степени: 1, 1, 2, 2. Есть две вершины с нечётной степенью. Это не эйлеров граф (но в нём есть эйлеров путь).
  • Граф 3: Вершины имеют степени: 3, 3, 3, 3. Все степени нечётные. Это не эйлеров граф.

Ответ: 1