На рисунке изображены два графа. Задание заключается в том, чтобы определить, сколько из них можно нарисовать, не отрывая карандаша от бумаги и проведя каждое ребро ровно один раз. Для решения этой задачи можно использовать правило Эйлера для графов, которое гласит, что для того чтобы граф можно было нарисовать одним непрерывным штрихом, необходимо, чтобы количество вершин с нечетным числом ребер было либо ноль, либо две.
Для первого графа: если посчитать количество рёбер, выходящих из каждой вершины, то можно заметить, что все вершины имеют четное количество ребер, за исключением двух вершин, из каждой из которых выходит три ребра (нечетное). По правилу Эйлера этот граф можно нарисовать одной линией.
Для второго графа: аналогичным образом, если посчитать ребра для каждой вершины, то можно увидеть, что четыре вершины имеют нечетное количество рёбер: по три ребра выходит из каждой этих вершин. Это означает, что нельзя будет нарисовать этот граф, не отрывая карандаша и не проведя некоторые ребра более одного раза.
Итак, из двух графов нарисовать по заданным условиям можно только первый.
