Построим следующий граф. Вершинами будут школьники. Две вершины соединим ребром, если соответствующие им школьники не знакомы. Нам надо узнать какое максимальное количество рёбер может быть в этом графе. Приведем пример при котором в этом графе 100 рёбер, а именно рассмотрим граф в виде цикла длины 100. Отметим любые 6 вершин и разобьём их на тройки так, что в каждой будут идущие через одну в цикле, тогда никакие две из одной тройки не соединены ребром. Докажем, что в нашем графе не может быть более 100 рёбер. В нашем графе нет вершины степени больше трёх. Иначе рассмотрим следующую шестёрку вершин-школьников 𝐴, четырёх её соседей 𝐵, 𝐶, 𝐷, 𝐸 и произвольную 𝐾. Тогда по построению графа школьник 𝐴 может жить в одной комнате только с 𝐾, что противоречит возможности поселить их по три человека знакомых друг с другом. Пусть есть вершина 𝑋 степени 3, её соседей обозначим через 𝑈, 𝑉, 𝑌 . Если есть ещё две вершины 𝑃 и 𝑄 отличные от этих четырёх соединённые ребром, то рассмотрим эту шестёрку школьников. 𝑋 может жить только с 𝑃 и 𝑄, которые не могут жить вместе. Значит все рёбра имеют одной из своих вершин одну из четырёх 𝑋, 𝑈, 𝑉, 𝑌 , а так как степень по доказанному выше у каждой не больше трёх то всего получается рёбер не больше 12 < 100. Если же из каждой вершины выходит не больше двух рёбер тогда их всего не больше 100 · 2 : 2 = 100. Мы доказали, что незнакомств максимум 100, тогда знакомств минимум 100 · 99 : 2 − 100 = 4950 − 100 = 4850.