Введение

Теорема Оре в теории графов — это результат, доказанный в 1960 году норвежским математиком Ойстейном Оре. Она дает достаточное условие для того, чтобы граф был гамильтоновым, по сути утверждая, что граф с достаточным количеством ребер должен содержать гамильтонов цикл. В частности, теорема рассматривает сумму степеней пар не смежных вершин: если сумма степеней каждой такой пары не меньше общего числа вершин в графе, то граф является гамильтоновым.

Официальное заявление

Пусть G – (конечный и простой) граф с n ≥ 3 вершинами. Обозначим deg v степенью вершины v в G, то есть число ребер, инцидентных вершине v в G. Тогда теорема Оре утверждает, что если

то G является гамильтоновым.

Доказательство

Это эквивалентно доказательству того, что каждый негамильтонов граф G не удовлетворяет условию (*). Следовательно, пусть G – граф на n ≥ 3 вершинах, который не является гамильтоновым, и пусть H формируется из G путем последовательного добавления ребер, не создающих гамильтонов цикл, до тех пор, пока добавление ребер станет невозможным. Пусть x и y – любые две несмежные вершины в H. Тогда добавление ребра xy к H создаст по крайней мере один новый гамильтонов цикл, и остальные ребра в этом цикле должны образовывать гамильтонов путь v1v2…vn в H, где v1 = x и vn = y. Для каждого индекса i в диапазоне 2 ≤ i ≤ n рассмотрим два возможных ребра в H: от v1 до vi и от vi-1 до vn. В H может присутствовать не более одного из этих двух ребер, иначе цикл v1v2…vi-1vnvn-1…vi был бы гамильтоновым циклом. Таким образом, общее количество ребер, инцидентных вершинам v1 или vn, не превышает числа возможных значений i, то есть n-1. Следовательно, H не удовлетворяет свойству (*), которое требует, чтобы это общее число ребер (deg v1 + deg vn) было больше или равно n. Поскольку степени вершин в G не превосходят степеней в H, следует, что G также не удовлетворяет свойству (*).

Сопутствующие результаты

Теорема Оре является обобщением теоремы Дирака, утверждающей, что если степень каждой вершины не меньше n/2, то граф является гамильтоновым. Действительно, если граф удовлетворяет условию Дирака, то степень каждой пары вершин в сумме не меньше n. В свою очередь, теорема Оре обобщается теоремой Бонди — Хваталя. Можно определить операцию замыкания для графа, заключающуюся в добавлении ребра между двумя несмежными вершинами, если сумма их степеней не меньше n. Если граф удовлетворяет условиям теоремы Оре, то его замыкание является полным графом. Теорема Бонди — Хваталя утверждает, что граф является гамильтоновым тогда и только тогда, когда его замыкание является гамильтоновым; поскольку полный граф является гамильтоновым, теорема Оре является непосредственным следствием. Была найдена версия теоремы Оре, применимая к ориентированным графам. Пусть ориентированный граф G обладает свойством, что для любых двух вершин u и v либо существует дуга от u к v, либо внешняя полустепень u плюс внутренняя полустепень v равна или превышает число вершин в G. Тогда, согласно теореме Вудалла, G содержит ориентированный гамильтонов цикл. Теорема Оре может быть получена из теоремы Вудалла путем замены каждого ребра в заданном неориентированном графе парой ориентированных дуг. Тесно связанная теорема утверждает, что сильно связный ориентированный граф на n вершинах, обладающий свойством, что для любых двух несмежных вершин u и v общее число ребер, инцидентных u или v, не меньше 2n − 1, должен быть гамильтоновым. Теорема Оре также может быть усилена, чтобы получить более сильное заключение, чем гамильтоновость, как следствие условия на степень в теореме. В частности, любой граф, удовлетворяющий условиям теоремы Оре, является либо регулярным полным двудольным графом, либо панциклическим.