В компании у каждых двух людей ровно пять общих знакомых. Докажите, что количество пар знакомых делится на 3. 
Обозначим через Р количество пар знакомых людей (то есть число рёбер в соответствующем графе), а через Т – количество треугольников в этом графе. По условию каждое из рёбер входит ровно в 5 треугольников. С другой стороны, в каждый из Т треугольников содержит ровно 3 ребра. Следовательно, 5Р = 3Т.  Поскольку 3 и 5 – взаимно простые числа, Р делится на 3. 
Теория графов (прочее) Подсчет двумя способами Делимость чисел. Общие свойства