Номер 142, часть 1 — ГДЗ Вероятность и статистика 7 класс Высоцкий, Ященко

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

Граф 1: две вершины, соединённые одним ребром; степени 1 и 1 — две нечётные вершины. Путь по единственному ребру, от одной вершины до другой, проходит каждое ребро ровно один раз. Граф эйлеров.

Граф 2: два отдельных ребра (граф несвязный), четыре вершины степени 1 — четыре нечётные вершины, а допустимо не больше двух. Нарисовать оба ребра одной непрерывной линией (одной ниткой) нельзя: от одного ребра нельзя перейти к другому. Граф не эйлеров.

Граф 3: цепь из четырёх вершин и трёх рёбер; степени 1, 2, 2, 1 — две нечётные вершины (концы цепи). Двигаясь вдоль цепи от одного конца к другому, проходим каждое ребро ровно один раз. Граф эйлеров.

Ответ: эйлеровы графы — 1 и 3.