Таблицы Брадиса

Докажем тогда, что М2к к2.

Докажем тогда, что М2к к2.

Элементы математики в задачах - Г. А. Мерзон

Введем обозначение: наибольшее возможное количество ребер в графе с п вершинами и свойством, что среди произвольных трех его вершин есть две, не соединенные ребром, будем называть Мп.

Нетрудно посчитать, что если соединять точки так, как описано выше, то Мп = к ■ к = к2, если п = 2к, и Мп = к(к + 1), если п = 2к + 1. Оказывается, что описанным выше способом мы действительно по­лучаем наибольшее возможное количество ребер. Поэтому докажем по индукции следующее утверждение: «Если п = 2к, то Мп = к2. Если же п = 2к +1, то Мп = к(к + 1)».

База индукции. При п = 2 и п = 3 утверждение очевидно.

Шаг индукции. Первый случай. Пусть для п = 2к — 1 утверждение верно. Докажем тогда, что М2к = к2. Предположим, что это не так.

Теория графов 1

То есть М2к > к2 (М2к < к2 быть не может, так как описанным выше способом мы умеем рисовать по крайней мере к2 ребер).

Лемма (вспомогательное утверждение). Рассмотрим граф Г с 2к вершинами, реализующий случай с М2к (> к2) ребрами. Докажем, что вершина минимальной степени (обозначим ее буквой а) в нем соединена не более, чем с к другими вершинами.

Действительно, предположим, что она соединена более чем с к вершинами: а1, а2,..., ак,... Возьмем одну из них. Например, а1. Ее степень не меньше, чем степень вершины а. А значит, она тоже соединена не менее чем с к вершинами: Ь1, Ь2,..., Ьк,... При этом (так как у нас «запрещены треугольники») ни одна из вершин а{ не совпадает ни с какой вершиной Ь. А значит, в нашем графе имеется по крайней мере 2к + 1 различная вершина, что противоречит наше­му предположению о количестве вершин графа Г.

Из утверждения леммы следует, что в рассматриваемом графе существует вершина, соединенная не более, чем с к другими вер­шинами. Если мы выкинем из графа эту вершину вместе со всеми ребрами, выходящими из нее, то получим граф с 2к — 1 вершиной и не менее, чем М2к — к > к2 — к = к(к — 1) ребрами. А это противоречит предположению индукции.