Теорема Фляйшнера — твердження в теорії графів, що дає достатню умову, щоб граф містив гамільтонів цикл: якщо граф є 2-вершинно-зв'язним, то квадрат графа гамільтонів. Названа ім'ям , який опублікував доведення теореми 1974 року.

Визначення та твердження Неорієнтований граф G є гамільтоновим, якщо він містить цикл, який проходить через кожну вершину рівно один раз. Граф є 2-вершинно-зв'язним, якщо він не містить зчленувальних вершин, тобто вершин, видалення яких робить граф, що залишився, незв'язним. Не будь-який 2-вершинно-зв'язний граф є гамільтоновим. Контрприкладами є граф Петерсена та повний двоковий граф K2,3.

Квадрат графа G — це граф G2, який має ту саму множину вершин, що й граф G, і в якому дві вершини суміжні тоді й лише тоді, коли відстань між ними в G не перевищує 2. Теорема Фляйшнера стверджує, що квадрат скінченного 2-вершинно-зв'язного графа з трьома і більше вершинами завжди гамільтонів. Еквівалентно, вершини будь-якого 2-вершинно-зв'язного графа G можна організувати в циклічний порядок, так що відстань у графі G між вершинами, суміжними в цьому порядку, не перевищує 2.

Розширення У теоремі Фляйшнера можна накласти обмеження на гамільтонів цикл так, щоб він включав три вибраних ребра, які проходять через дві вибрані вершини.

Крім наявності гамільтонового циклу, квадрат 2-вершинно-зв'язного графа G має бути також гамільтоново пов'язаним (що означає, що він має гамільтонів шлях, який починається і закінчується в будь-яких двох вибраних вершинах) і 1-гамільтонів (що означає, що якщо видалити будь-яку вершину, граф, що залишився, також міститиме гамільтонів цикл). Граф має бути також вершинно панциклічним, що означає, що для будь-якої вершини v та будь-якого цілого k з 3 ≤ k ≤ |V(G)| існує цикл довжини k, що містить vХоббс (), відповідь на гіпотезу Бонді (). .

Якщо граф G не 2-вершинно-зв'язний, його квадрат може мати, а може і не мати гамільтонового циклу і визначення, чи має граф такий цикл, є NP-повною задачею.

Нескінченний граф не може мати гамільтонового циклу, оскільки будь-який цикл скінченний, але довів, що у випадку, коли G є нескінченним локально скінченним 2-вершинно-зв'язним графом з єдиним кінцем, то G2 обов'язково має двічі нескінченний гамільтонів шлях. Загальніше, якщо G локально скінченний, 2-вершинно-зв'язний і має будь-яке число кінців, то G2 має гамільтонів цикл. У компактному топологічному просторі, утвореному розглядом графа як симпліційного комплексу і доданням точки на нескінченності для кожного кінця графа, гамільтонів цикл визначають як підпростір, який гомеоморфний евклідовому колу і покриває всі вершини.

Історія Про доведення теореми оголосив 1971 року й опублікував 1974 року, вирішивши цим гіпотезу 1966 року , яку незалежно висловили також і . Про раніші гіпотези див. у Фляйшнера і Чартранда, Лесняка і Чжана ().. У своєму огляді статті Фляйшнера Неш-Вільямс пише, що той вирішив «добре відому проблему, об яку кілька років розбивалася винахідливість інших теоретиків теорії графів»..

Оригінальне доведення Фляйшнера було складним. Вацлав Хватал у праці, в якій він увів поняття жорсткості графа, зауважив, що квадрат k-вершинно-зв'язного графа обов'язково k-жорсткий. Він висловив припущення, що 2-жорсткі графи є гамільтоновими, з чого вийшло б інше доведення теореми Фляйшнера. Пізніше виявлено контрприклади до цієї гіпотези, але можливість, що зі скінченної межі жорсткості могла б випливати гамільтоновість, залишилася важливою відкритою проблемою теорії графів. Простіше доведення як теореми Фляйшнера, так і її розширень, які зробили Чартранд, Хоббс, Янг і Капуур, надав Ріха, а ще одне спрощене доведення теореми надав Георгакопулус.

Примітки

Література