'''ГіпотезаГіпо́теза БарнеттаБа́рнетта''' є [[припущення]]м в [[Теорія графів|теорії графів]], розділ [[математика|математики]], щодо [[гамільтонів граф|гамільтонових]] циклів в графах. Вона названа на честь [[Девіда У. Барнетта]], [[емеритура|почесного професора]] [[Каліфорнійський університет у Девісі|Каліфорнійського університету в Девісі]]. В ньому йдеться, що кожен [[двочастковий граф|двочастковий]] [[багатогранний граф]] з [[кубічний граф|трьома ребрами на вершині]] має гамільтонів цикл.
== Визначення ==
Рядок 8:
== Історія ==
{{Нп|Пітер Гатри Тейт|||Peter Tait (physicist)}} висловив припущення, що кожен кубічний багатогранний граф є гамільтоновим; це стало відомо як {{Нп|гіпотеза Тейта|||Tait's conjecture}}. Це було спростовано [[ВіллемВільям Татт|ВіллемомВільямом Таттом]], який побудував [[контрприклад]] з 46 вершинами; інші дослідники пізніше знайшли ще менші контрприклади. Проте жоден з цих відомих контрприклад не є дводольним. Сам Tutte висловив припущення, що кожен кубічний 3-зв'язний двочастковий граф є гамільтонів, але це було показано помилковим виявленням контрприкладу, [[граф Хортона]] запропонував поєднання домислів Тейта і Tутте, заявивши, що кожен двочастковий кубічний поліедр гамільтоновів, або, що те ж саме, що кожен контрприклад до гіпотези Тейта не є дводольним.
