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

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

Last modified: Saturday, 4 July 2020, 3:03 PM