Problem

Source: Kyiv City MO 2023 Round 1, Problem 11.5

Tags: combinatorics, graph theory



In a galaxy far, far away there are $225$ inhabited planets. Between some pairs of inhabited planets there is a bidirectional space connection, and it is possible to reach any planet from any other (possibly with several transfers). The influence of a planet is the number of other planets with which this planet has a direct connection. It is known that if two planets are not connected by a direct space flight, they have different influences. What is the smallest number of connections possible under these conditions? Proposed by Arsenii Nikolaev, Bogdan Rublov