№12. Сколько графов, изображенных на рисунке, можно нарисовать, не отрывая карандаша от бумаги и проводя каждое ребро ровно один раз?

Чтобы граф можно было нарисовать, не отрывая карандаша от бумаги и проводя каждое ребро ровно один раз, необходимо, чтобы он был эйлеровым или полуэйлеровым. Это означает, что количество вершин с нечетной степенью должно быть либо 0, либо 2. Граф 1: Имеет 5 вершин, 4 из которых имеют степень 3 (нечетная), и одна вершина имеет степень 4 (четная). Так как вершин с нечетной степенью больше двух, этот граф нельзя нарисовать одним росчерком. Граф 2: Имеет 4 вершины, все из которых имеют степень 3 (нечетная). Так как вершин с нечетной степенью больше двух, этот граф нельзя нарисовать одним росчерком. Таким образом, ни один из графов нельзя нарисовать, не отрывая карандаша. Следовательно, ответ: 0.