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

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