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

• Первый граф имеет 4 вершины со степенью 3 и 1 вершину со степенью 4.
• Второй граф имеет 4 вершины со степенью 3.
• Эйлеров цикл (возможность нарисовать граф, не отрывая карандаша и не проходя по одному ребру дважды) существует только в том графе, где все вершины имеют четную степень.

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

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

Граф можно нарисовать одним росчерком, если в нём не более двух нечётных вершин.

В первом графе 4 вершины нечетные. Значит его нельзя нарисовать одним росчерком.

Во втором графе 4 вершины нечетные. Значит его нельзя нарисовать одним росчерком.

Следовательно, ни один из графов нельзя нарисовать одним росчерком.

Граф можно нарисовать одним росчерком, если в нём не более двух нечётных вершин. В первом графе 4 вершины нечетные. Значит его нельзя нарисовать одним росчерком. Во втором графе 4 вершины нечетные. Значит его нельзя нарисовать одним росчерком. Следовательно, ни один из графов нельзя нарисовать одним росчерком.

Первый граф можно нарисовать, начав с вершины, имеющей нечетную степень (например, верхней вершины), и закончив в другой вершине, имеющей нечетную степень.