62nd Ukrainian National Mathematical Olympiad

Let's reformulate this problem in terms of graphs. Planets are vertices of the graph, direct flights are edges. It is known that in any graph, any two vertices that are not connected by an edge have different degrees. The question is how many edges can be in such a graph, the number of vertices being irrelevant. First, let's prove the following lemma.

Lemma 1. In a graph, there are no more than $k+1$ vertices of degree $k$ for any natural number $k$.

Proof. By contradiction. Let $M$ be a set of at least $k+2$ vertices, each of which has degree $k$. If at least two vertices in $M$ are not connected, then the condition of the problem is violated. Thus, every two vertices in $M$ are connected. But then the degree of each vertex is at least $k+1$, which contradicts the condition. This contradiction completes the proof.

Lemma proved.

Lemma 2. For any natural number $k\ge 3$, if the minimum number of edges in a simple graph, then there are at most $k$ vertices of degree $k$.

Proof. By contradiction. From the previous lemma, there can be at most $k+1$ vertices of degree $k$. If there are fewer than $k+1$, then the statement is proven. Suppose that for some $k$, there exists a vertex of degree $k+1$. But then they are all connected to each other and there are no other vertices in the graph. Thus, we have a complete graph on ($k+1$) vertices.

Now consider a complete graph on $k$ vertices and one vertex connected to one of the $k$ vertices. Then, there is one vertex of degree 1, one vertex of degree $k$, and $k-1$ vertices of degree $k-1$. Thus, the vertices not connected to the added vertex have different degrees. Let's count the number of edges for both cases. For the complete graph on ($k+1$) vertices, there are $\frac{1}{2}k(k+1)$ edges, and for the second case, a complete graph on $k$ vertices with an additional edge, there are $\frac{1}{2}(k-1)k+1$ edges.

Then, $$\frac{k(k+1)}{2}>\frac{(k-1)k}{2}+1\iff k^2+k>k^2-k+2\iff k>1,$$ so the number of edges has decreased. This contradiction completes the proof of the lemma.

Lemma 3. If we decrease the degree of at least one vertex in a graph, the total number of edges will decrease.

Proof. It is sufficient to recall the formula for the sum of the degrees of all vertices $S$ and the number of edges $R$. Clearly, $S=2R$. Therefore, if $S$ decreases, $R$ also decreases.

Lemma proved.

Thus, let us assume we have 225 vertices. We will find a value of $k$ for which the following inequality holds: $$1+2+\cdots +k=\frac{k(k+1)}{2}\le 225<1+2+\cdots +k+(k+1)=\frac{(k+1)(k+2)}{2}.$$ This value of $k$ is 20. Let $$l=225-(1+2+\cdots +k)=225-210=15.$$ Then for the minimum number of edges, we should have 1 vertex of degree 1, 2 vertices of degree 2, ..., $k$ vertices of degree $k$. For the remaining $l$ vertices, there are several options. The smallest number of edges would be if all these vertices had degree $k+1$. But then the total number of edges leaving each vertex would be: $$L=1\cdot 1+2\cdot 2+\cdots +20\cdot 20+15\cdot 21=3185.$$ In this count, each edge is counted twice, so this number should be even. Since this number is odd, the minimum number of edges should be $\frac{1}{2}(L+1)=1593$. For this case, there should be 14 vertices of degree 21 and 1 vertex of degree 22. It remains to show that such a situation is possible.

In this way, we should have 1 vertex of degree 1, 2 vertices of degree 2, ..., 20 vertices of degree 20, 14 vertices of degree 21, and 1 vertex of degree 22. It remains to construct an example of a graph that satisfies the conditions of the problem. First, we build complete graphs for vertices of degree 2, 3, ..., 20. Then we build a complete graph for the remaining 15 vertices. Thus, the condition of having vertices with the same degree is satisfied.

Next, we need to make the graph connected and ensure that no pair of vertices is connected twice. The following edges remain unconnected: 1 edge for each vertex of degrees 1 through 20, and from the last group of 15 vertices, we have 14 vertices of degree 7 and 1 vertex of degree 8, where the last vertices are already connected. This follows from the fact that they are connected to each other by 14 edges. Thus, the first group has $1+2+\cdots +20=210$ edges, and the second group has $14\cdot 7+8=106$ edges. We then connect each group from degree 1 to degree 20 with a common edge, and connect the last group to the vertex of degree 8 (Fig. 10).



Fig. 10

In this way, we use 39 edges from the first group of 210 edges and 1 edge from the second group of 106 edges, and achieve a connected graph. We are left with 105 edges that need to be connected to the 105 edges from the first group, but in a way that evenly distributes them, starting from the groups with the maximum number of edges. Obviously, the remaining edges can be connected easily.