Чтобы решать задачи на рисование графов без отрыва карандаша, нужно определить чётность или нечётность всех вершин графа. 3 Чётность вершины указывает на число рёбер, которое из неё выходит. 3 Если из вершины выходит чётное число рёбер, то она чётная, а если нечётное — нечётная. 3

Правила решения задач: 3

• Если все вершины чётные, то граф можно начертить одним росчерком, не отрывая карандаша от бумаги. 35 При этом можно начинать с любой вершины графа, а завершаться он будет в этой же точке. 3
• Если ровно две вершины графа нечётные, то его можно начертить одним росчерком, не отрывая карандаша от бумаги. 35 При этом начать следует с одной из нечётных вершин, а завершать — во второй нечётной вершине. 3
• Если в графе три и больше нечётных вершин, то его невозможно начертить одним росчерком, не отрывая карандаша от бумаги, и не проводя по одному ребру дважды. 3

Граф, который можно нарисовать, не отрывая карандаша от бумаги, называется эйлеровым. 5