Грид граф p x q  има p.q върха.  Ако p и q са нечетни, то броят на върховете е нечетен.  Очевидно Хамилтонов цикъл, ако такъв има, има дължина, равна на броя на върховете.  Следователно, ако имаше Х. цикъл, той би бил с нечетна дължина.

От друга страна, всеки грид граф е двуделен.  А знаем, че граф е двуделен тстк няма нечетни цикли.  QED

Последно модифициране: събота, 4 юли 2020, 15:03