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

Чтобы определить, можно ли нарисовать граф, не отрывая карандаша от бумаги, нужно проверить следующие условия: obuchonok.ru otvet.mail.ru

1. Если все вершины графа чётные, то его можно начертить одним росчерком, проводя по каждому ребру только один раз. obuchonok.ru Движение можно начать с любой вершины и закончить его в той же вершине. obuchonok.ru
2. Граф, имеющий всего две нечётные вершины, можно начертить, не отрывая карандаш от бумаги. obuchonok.ru При этом движение нужно начать с одной из этих нечётных вершин и закончить во второй из них. obuchonok.ru
3. Граф, имеющий более двух нечётных вершин, невозможно начертить одним росчерком. obuchonok.ru

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