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

Напомним (п. 21): эйлеров граф — это граф, в котором есть эйлеров путь, то есть путь, проходящий ровно один раз по каждому ребру. Если у связного графа не больше двух вершин нечётной степени, то эйлеров путь есть; если вершин нечётной степени больше двух, пути нет. А несвязный граф одним путём «обойти» нельзя совсем: из одной его части в другую не перейти. Вершины на рисунке — отмеченные точки; места, где линии пересекаются без точки (граф 2), вершинами не считаются. Около вершин записаны их степени.

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

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

Граф 3: внешний цикл из пяти вершин и два ребра, соединяющие две внутренние вершины («чечевица»). Эти две части между собой не связаны, поэтому граф несвязный: одним путём нельзя пройти и внешний цикл, и внутренние рёбра. Хотя все степени чётные, граф не эйлеров.

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

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