Задача по графам. Олимпиадная.

У нас есть простой неориентированный граф (без циклов, без нескольких ребер) со странным свойством: любые две разные вершины имеют ровно два общих соседа. Утверждение состоит в том, что граф должен быть регулярным (степени вершин все одинаковы).
Итак, давайте рассмотрим, что происходит прямо вокруг двух людей, А и Б, которые знают друг друга.
Рассмотрим любого друга А, кроме Б. Назовем это А'. У него ровно два общих соседа с B. Один из этих общих соседей это A, а другой... кто-то другой. Назовем это Б'. Ясно, что Б' находится среди друзей Б, и это не А . Кроме того, это единственный и неповторимый друг Б, который не является А и знает А'. Верно? В противном случае у A' и B было бы слишком много общих друзей.
Итак, учитывая человека А', который знает А и не является Б, мы смогли найти специального человека Б', который знает Б и не является А. Что делает их особенными, так это то, что они являются уникальным общим другом A' и B, отличным от A. Еще одна вещь, которая делает их особенными, - это то, что они одни среди друзей Б, которые не являются А, которые знают А'.
Это обеспечивает функцию f:U→V, где U - друзья A (кроме B), а V - друзья B (кроме A). Функция переводит A' в этот единственный B'. И, конечно же, точно так же рассуждая, мы получаем функцию g:V→U, переводящую некоторого друга B' из B (но не A) в их единственного друга из U.
Ясно, что отображения f и g обратны друг другу, что доказывает, что |U|=|V|. Отсюда следует, что у A и B одинаковое количество друзей (что означает deg(A)=deg(B)).
Но A и B были произвольными связными вершинами. Поскольку весь граф явно связан, мы заключаем, что степень постоянна по всему графу.
P.S. На данный момент мы находимся в странном положении: мы доказали, что граф с данным специфическим свойством должен быть регулярным, но мы даже не знаем, что такой граф существует. Существует множество обычных графиков, но если вы на мгновение рассмотрите их, то, похоже, они не удовлетворяют свойству двух общих друзей. Собственно, у одного из них есть, и его нетрудно найти. Простейший регулярный граф - это K_n, полный граф с n вершинами. Каждые две вершины в этом графе имеют ровно n-2 общих соседей (каждую вершину, кроме них самих!), Поэтому мы можем взять n=4 и заметить, что K_4 действительно обладает требуемым свойством. Это оно? Если это так, то вывод нашей теоремы совершенно неадекватен. Вместо того чтобы утверждать, что «граф должен быть регулярным», мы должны утверждать, что «граф должен быть изоморфен K_4». Возможно, что удивительно, но это не так. Еще один граф с этим свойством - декартово произведение K_4×K_4, представляющее собой сетку 4×4, где все знают всех в одной строке и одном столбце. Проверь, это весело). Это 6 -регулярный граф с 16 вершинами, удовлетворяющий нашему странному свойству.