.В группе из 25 человек любые двое имеют общего знакомого. Докажите, что из этой группы можно не менее, чем 36 способами выбрать пару знакомых школьников. Даю 30 баллов

Представим учеников, как вершины графа, а их знакомства, как рёбра. По условию, в данном графе 25 вершин и любые две вершины соединены рёбрами с общей вершиной.

Докажем от противного. Пусть в графе не больше 35 рёбер. Допустим, что найдётся вершина степени 1, тогда рассмотрим её и вершину, соединённую с ней ребром. Они не имеют "общей вершины", так как та, которая имеет степень 1, не соединена больше ни с одной вершиной. Если найдётся вершина степени 0, условие не выполняется для неё точно. Допустим, что в графе не найдётся вершины степени 2, тогда степень каждой вершины не меньше 3, а суммарная степень вершин не меньше 75. Но тогда в графе не меньше 38 рёбер. Значит, найдётся вершина степени 2. Рассмотрим её. Она соединена с двумя вершинами (2 ребра). Каждая из остальных 22 вершин должна иметь "общую вершину" с этой, значит, каждая из оставшихся вершин соединена ребром с одной из этих двух (ещё 22 ребра) (это для того, чтобы "вершина степени 2" имела "общую вершину" с каждой из остальных). Рассмотрим "эти две вершины", они должны иметь "общую вершину" с каждой из тех, с которыми соединены, значит, должны быть соединены и между собой (ещё одно ребро) (чтобы "вершина степени 2" и каждая из "этих двух вершин" имела "общую вершину"). Так как степень остальных вершин должна быть не меньше 2, то нужно ещё не менее 11 рёбер. Итого в графе не менее 36 рёбер, что больше 35.

Эти 36 рёбер и есть искомые 36 способов выбрать пару знакомых школьников.

Школьник  А   знаком  с  двумя  школьниками   Б  и  В.   Б  и  В  должны быть тоже знакомы,  иначе  у  них  не  будет общего знакомого  А.

Поделим  знакомство   Б  и  В  с  остальными  22  школьниками.

Получится,  у  Б  и  В  по  13  знакомств   (2+11).  На двоих  2*13=26 знакомств.

Но,  чтобы  у  22  тоже  было  по  2 знакомства  они  должны перезнакомиться,  между собой   11  с  11  другими.

Школьник   А  и  22  школьника  имеют  по  2  знакомства  23*2= 46 знакомств.

Итого:   26 + 46= 72.

Каждое  знакомство  учитывалось  дважды ( А с Б  и  Б с А,  и  так  далее).

Поэтому  способов  в  2  раза  меньше  72:2=36.