В графе на n вершинах для любой пары вершин u и v есть ровно две вершины, с которыми соединены и u, и v. Докажите, что степени всех вершин в этом графе одинаковы.

Рассмотрим некоторую вершину X, пусть ее степень равна x. По условию для каждой пары соседей X четвертая вершина определяется единственным образом (обозначим множество соседей X за G(X)). Заметим, что все вершины для таких пар различны, так как иначе найдутся две вершины из
множества соседей X, у которых будет 3 общих соседа.
Докажем, что у каждой вершины из множества G(X) степень равна x. У любой пары вершин из G(X) по условию будет два соседа: один из них – вершина X, второй – некая другая вершина не из множества G(X), причем по доказанному все такие вершины различны. Тогда каждая вершина из G(X) соединена с X и с еще x − 1 вершиной вне множества G(X) (так как именно x − 1 пару можно составить для каждой конкретной вершины). Тогда степень каждой вершины G(X) хотя бы
x − 1 + 1 = x. С другой стороны, если у какой-либо вершины A степень будет хотя бы x + 1, то найдется вершина Y , соединенная с A. Тогда для вершин X и Y найдется ровно 2 вершины, с которыми они обе соединены, причем одна из них – вершина A. Пусть вторая вершина – вершина B, которая принадлежит множеству G(X) (так как X с ней соединен). Но тогда у вершин A и B уже есть минимум 3 общих соседа – X, Y и некоторая вершина C вне множества G(X) – противоречие.
Получим, что степень каждой вершины в G(X) равна x.
Очевидно, что граф связный, так как если в нем есть хотя бы 2 компоненты, то можно выбрать по одной вершине из каждой и для них найдется пара вершин, с которыми соединены эти две вершины. Тогда аналогичными рассуждениями получим, что все соседи вершины A имею степень x, соседи этих соседей имеют степень x и так далее. Получим, что степени всех вершин в таком графе будут равны x – ЧТД.