Теорема Турáна даёт ответ на вопрос о максимальном количестве рёбер в графе без полного n-вершинного подграфа .

Впервые задачу о запрещённом подграфе поставил венгерский математик Пал Туран в 1941 году .

Формулировка

Обозначения

Обозначим через ${\displaystyle K_{n}}$ полный n-вершинный граф.

Определим граф ${\displaystyle T_{n}(v)}$ с ${\displaystyle v}$ вершинами следующим образом. Разобьём все вершины на ${\displaystyle n-1}$ «почти равных» групп (то есть возьмём ${\displaystyle r}$ групп по ${\displaystyle m+1}$ вершине и ${\displaystyle n-1-r}$ групп по ${\displaystyle m}$ вершин, где ${\displaystyle v=m(n-1)+r}$ , здесь ${\displaystyle r}$ — остаток от деления ${\displaystyle v}$ на ${\displaystyle n-1}$ ) и соединим рёбрами все пары вершин из разных групп. Таким образом получим ${\displaystyle (n-1)}$ -дольный граф.

Будем обозначать через ${\displaystyle ex(v,n)}$ максимальное количество рёбер, которое может иметь граф с ${\displaystyle v}$ вершинами, не содержащий подграфа, изоморфного ${\displaystyle K_{n}}$ .

Теорема

Среди всех графов на ${\displaystyle v}$ вершинах, не содержащих подграфа ${\displaystyle K_{n}}$ , максимальное количество рёбер имеет граф ${\displaystyle T_{n}(v)}$ . Если ${\displaystyle v=m(n-1)+r}$ , где ${\displaystyle r}$ — остаток от деления ${\displaystyle v}$ на ${\displaystyle n-1}$ , то этот максимум равен

${\displaystyle ex(v,n)={\frac {(n-2)(v^{2}-r^{2})}{2n-2}}+{\frac {r(r-1)}{2}}}$

Замечания

• При ${\displaystyle n\leq 8}$ основную формулу можно записать короче:

  ${\displaystyle ex(v,n)=\left[v^{2}\cdot {\frac {n-2}{2n-2}}\right]}$ .

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

Доказательство можно провести, например, с помощью математической индукции по количеству вершин графа ${\displaystyle v}$ .

Введем индукцию по числу вершин ${\displaystyle n}$ в полном подграфе.

• База ${\displaystyle n=3}$ . Доказательство: Введем индукцию по числу вершин.
  • База ${\displaystyle n=1,2}$ . Для данных случаев оценка очевидна.
  • Шаг: Пусть доказано для ${\displaystyle k}$ . Докажем для ${\displaystyle k+2}$ . Если в графе нет ребер то все доказано. Иначе выделим ребро. Заметим что к этому ребру из остальных вершин графа выходит не более одного ребра (иначе есть треугольник) ${\displaystyle \Rightarrow }$ этих ребер не более ${\displaystyle k}$ . Для остального графа применим предположение индукции. Откуда общее количество рёбер не более ${\displaystyle {\frac {k^{2}-r^{2}}{4}}+k+1={\frac {(k+2)^{2}-r^{2}}{4}}}$ . Что и требовалось.
• База доказана.

• Шаг. Пусть для ${\displaystyle n-1}$ верно, докажем для ${\displaystyle n}$ . Введем индукцию. База ${\displaystyle k=1,2,\ldots ,n-1}$ . Для данных случаев утверждение очевидно. Шаг. Пусть для ${\displaystyle k}$ верно, докажем для ${\displaystyle k+n-1}$ . Если в графе нет полного графа на ${\displaystyle n-1}$ вершинах воспользуемся предыдущим шагом (очевидно, что оценка будет лучше). Иначе выделим его. Из каждой из остальных вершин к нему выходит не более ${\displaystyle n-2}$ ребер, то есть всего не более ${\displaystyle k\cdot (n-2)}$ . Следовательно, общее количество рёбер в графе не превышает

$${\displaystyle {\frac {(n-2)(k^{2}-r^{2})}{2n-2}}+{\frac {(n-1)(n-2)}{2}}+k\cdot (n-2)+{\frac {r\cdot (r-1)}{2}}={\frac {(n-2)((k+n-1)^{2}-r^{2})}{2n-2}}+{\frac {r\cdot (r-1)}{2}}}$$

Что и требовалось. Шаг индукции доказан.

Вариации и обобщения

• Доказательство теоремы Турана влечёт несколько более сильный результат: для любого графа ${\displaystyle \Gamma }$ не содержащего копию полного графа ${\displaystyle K_{n+1}}$ найдётся ${\displaystyle n}$ -дольный граф ${\displaystyle \Gamma '}$ с тем же множеством вершин, что и ${\displaystyle \Gamma }$ и со степенью каждой вершины не меньше чему у ${\displaystyle \Gamma }$ .

Литература

• «Теория графов» О.Оре. 1980
• Berge C. Graphs (second revised edition), North — Holland, Amsterdam — New York — Oxford, 1985.
• Lovasz L. Combinatorial problems and exercises, Academiqi Kiado, Budapest, 1979.

Внешние ссылки