Question

(это лемма Турана) В графе 2n вершин и n^2+1 ребро. Доказать, что в графе есть хотя бы один треугольник.Можно ооочень подробно и понятно, пожалуйста

Answer 1

Построим таблицу 2n×2n (см. рис). Столбцы и строки обозначают вершины (они занумерованы числами от 1 до 2n). Если какие-то вершины соединены ребром, то на соответствующем пересечении столбца и строки напишем 1. Например, если вершины 4 и 2 соединены ребром, то на пересечении 4 столбца и 2 строки напишем 1. Поскольку 4 столбец и четвертая строка отвечают за одну и ту же вершину, можем обрезать таблицу пополам (по линии диагонали). Заметим, если три вершины образуют треугольник, то единицы, соответствующие этим соединениям образуют прямоугольный треугольник (если мысленно их соединить в таблице). Также, любой двойке единиц в конкретном столбце соответствует единственная единица в соответствующей строке, такая что они втроем образуют треугольник. Например, на рисунке красные единицы образуют треугольные, а синие - нет. При этом двойке красных единиц в 4-ом столбце соответствует единственная 1-ца, такая, что они вместе образуют треугольник (если бы третья единица была в 3-ем столбце, 1 строке, то треугольник не образовывался). Значит общее число треугольников в графе соответствует сумме комбинаций двоек в каждом столбце. Пусть в первом столбце n₁ единиц, во втором n₂ и т.д. Значит общее число треугольников равно  $\frac{n_{1}(n_{1}-1)}{2}+ \frac{n_{2}(n_{2}-1)}{2}+...+ \frac{n_{2n}(n_{2n}-1)}{2}= \frac{n_{1}^{2}+n_{2}^{2}+...+n_{2n}^{2}-n^{2}-1}{2}$(*); Заметим, что минимальное значение выражения A²-A для натуральных чисел равно 1. Раз   $n_{1}^{2}+n_{2}^{2}+...+n_{2n}^{2}-n_{1}-n_{2}-...-n_{2n}=2n$, то с учетом (*), минимальное количество треугольников равно 2n/2 = n; То есть ясно, что хотя бы один треугольник образуется

Answer 2

Давайте рассмотрим граф с 2n вершинами и n^2 + 1 ребром, и докажем, что в нем существует хотя бы один треугольник.

1. Количество вершин и рёбер: - У нас есть 2n вершин. - И n^2 + 1 ребро.

2. Рассмотрим степени вершин: - По теореме о рукопожатиях для графа, сумма степеней всех вершин равна удвоенному числу рёбер. Так как у нас есть n^2 + 1 ребро и 2n вершин, средняя степень вершины равна (n^2 + 1) / (2n). 3. Рассмотрим минимальную и максимальную степени: - Минимальная степень вершины в графе не может быть больше нуля (поскольку нет изолированных вершин), а, следовательно, минимальная степень равна 1. - Максимальная степень вершины в графе не может превышать n^2, так как у нас есть n^2 + 1 ребро и каждое ребро инцидентно двум вершинам. Таким образом, максимальная степень не может превышать n^2.

4. Рассмотрим среднюю степень вершины: - Если средняя степень вершины больше n, то существует хотя бы одна вершина со степенью, превышающей n, что невозможно в нашем графе.

5. Вывод: - Из пунктов 3 и 4 следует, что средняя степень вершины не может быть больше n. Однако, учитывая, что минимальная степень равна 1, должна существовать хотя бы одна вершина со степенью, меньшей или равной n.

6. Поиск треугольника: - Пусть вершина A имеет степень k <= n. Это означает, что существует как минимум n - k вершин, смежных с A. Если две из этих вершин также соединены ребром между собой (то есть образуют ребро треугольника с вершиной A), то мы нашли треугольник. В противном случае, у нас есть как минимум n - k - 1 вершина, смежных с обеими вершинами A и B. Если хотя бы две из них также соединены ребром между собой, то мы снова находим треугольник. Продолжая этот процесс, мы рано или поздно найдем треугольник.

Таким образом, мы доказали, что в графе с 2n вершинами и n^2 + 1 ребром существует хотя бы один треугольник.