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

Будем доказывать по индукции утверждение, что в графе из 2n вершин без треугольников не более
$ n^2 $ ребер.
База: n = 2
При добавлении хотя бы 1 ребра получится треугольник
Переход от n к n + 1:
Рассмотрим граф N на 2n + 2 вершинах без треугольников. Рассмотрим вершины A и B со степенями a и b соответственно, соединенные ребром. Удалим из графа эти вершины и ребра, исходящие из них. Получим граф M на 2n вершинах без треугольников (т.к. их не было в исходном графе, а после удаления вершин треугольники не могли появиться), в котором по предположению индукции может быть не больше, чем $ n^2 $ ребер.
Так как в графе N нет треугольников, то у вершин A и B не могло быть общей вершины C. Тогда в сумме из вершин A и B не могло выходить больше, чем 2n + 1 ребер (2n в вершины, помимо A и B, и одно ребро, соединяющее A и B). Тогда в исходном графе N содержится не больше, чем $ n^2 + 2n + 1 = (n + 1)^2 $ – доказано.
Получим, что в любом графе на 2n вершинах без треугольников не больше, чем $ n^2 $ ребер.
Тогда если по условию дан граф на 2n вершинах с $ n^2 + 1 $ ребрами, то в нем найдется хотя бы 1 треугольник (3 смежные вершины)