The country has $n \ge 3$ airports, some pairs of which are connected by bidirectional flights. Every day, the government closes the airport with the strictly highest number of flights going out of it. What is the maximum number of days this can continue? Proposed by Fedir Yudin
Problem
Source: Ukrainian Mathematical Olympiad 2023. Day 2, Problem 8.7
Tags: combinatorics, graphs, Hi
06.04.2023 03:33
The answer is $1$ for $n=3$ and $n-3$ for $n \ge 4$. Construction For $n=3$, take $K_{2,1}$. For $n \ge 4$, construct the graph $G_n$ on $\{1, \dots, n\}$ where $i < j$ are adjacent if and only if $j-i \ge 2$ and $(i,j) \neq (1,3)$. In this graph, $n$ is the unique highest degree vertex and deleting it gives $G_{n-1}$. Bound The $n=3$ and $n=4$ cases can be checked by brute-force. For $n > 4$, note that we reach a graph on four vertices after $n-4$ moves, at which point at most one more move is possible by said brute-force.
07.04.2023 13:55
OOPS I misinterpreted the problem as: "Given a graph on $n$ vertices, take the $n$ corresponding degrees and sort them in decreasing order. Find the longest possible prefix where all degrees are distinct." Basically, a flight can still go out of an open airport to a closed one. Anybody knows how to solve it in this case? For $n=4,5,6,7$ the answer is still $n-3$ but for $n=8$ it becomes $4$ so IDK.
03.09.2023 17:04
The answer is $1$ for $n=3$ and $n-3$ otherwise. For the bound, notice that the answer is $1$ for $n=3$ and $n=4$ by brute force, and then the conclusion easily follows. For construction, take a triangle missing an edge for $n=3$. For $n \geq 4$, inductively construct a graph on the vertices $v_1, v_2, \dots, v_n$ in a line, such that $v_i$ and $v_j$ are connected iff they are nonconsecutive, and $v_1$ is not connected to $v_3$. Then, $v_n$ is the highest-degree vertex, and deleting $v_n$ yields the identical graph with $n-1$ vertices, as needed.
26.12.2023 16:07
Solved with akliu. For $n = 3$, the answer is $1$, and for $n \ge 4$, the answer is $n -3 $. The construction for $n = 3$ is just a graph on $3$ vertices with two edges. For $n\ge 4$, label the vertices $v_1, v_2,\ldots, v_n$. Connect $v_1$ with $v_2, v_3, \ldots, v_{n-1}$, connect $v_n$ to $v_2, v_3, \ldots, v_{n-2}$, then $v_{n-1}$ to $v_2, v_3, \ldots, v_{n-3}$, and so on until $v_5$ to $v_2, v_3$. One can check that such a construction works (first delete $v_1$, then $v_n$, then $v_{n-1}$, and so on). The bound for $n = 3$ can be easily checked since there aren't many simple graphs with $3$ vertices. For $n = 4$, suppose we could make two moves. Then, our first move must delete a vertex with degree at least $2$. If the vertex deleted first has degree $2$, then the next deletion must have degree $1$, absurd since the vertex adjacent to it also has degree $1$. Therefore, the vertex deleted first has degree $3$. Since it is the maximal degree, after deletion all degrees are at most $1$, so clearly we can't have any more deletions. For $n > 4$, notice after we make a move, we reach a position for $n - 1$, so we can perform at most $n - 4$ moves, hence we can only perform $n - 3$ moves.
01.01.2024 21:35
$F_n$ denote the answer. Note that $F_3 = F_4 = 1$. Take the following condition for $F_4$ construction: [asy][asy] pair A = (-0.5,0.5); pair B = (-0.5,-0.5); pair C = (0.5,-0.5); pair D = (0.5,0.5); import graph; size(3cm); draw(A--B, linewidth(0.5)); draw(A--C, linewidth(0.5)); dot("$A$", A, NW); dot("$B$", B, SW); dot("$C$", C, SE); dot("$D$", D, NE); [/asy][/asy] Now note that if we have $F_{n+1}$ and delete one vertex that has strictly maximal degree, then we end up with $F_n$. So it takes $n-3$ moves. Now for the construction, take $f_n$ with $n\ge 4$ and we show for $F_{n+1}$. Add in a vertex and connect it with all the other vertices except the one with the maximal degree. Note that in $F_n$, then maximal degree is $n-2$, and so, in $F_{n+1}$ is $n-1$ and our induction is complete.
09.04.2024 06:50
The answer is $1$ for $n=3$ and $n-3$ for $n\geq 4$. For $n=3$ the answer is clear. For $n=4$, since degree 1 cannot be unique, the deleted degrees must be 2 and 3 if we were to achieve 2. However, if we have a degree 3 vertex, any vertex that remains degree 2 after deletion has degree 3 at the start, contradiction. This also establishes the bound in general, as we are at $n-4$ when we reach 4 vertices, and we can make at most one more move. For the construction, label the vertices $V_1\dots V_n$. Then, connect every pair of vertices EXCEPT for $V_i,V_{i+1}$ for $1\leq i\leq n-1$ and $V_{n-2},V_n$. This leads to degrees of $n-2,n-3,n-3\dots,n-3,n-4,n-3,n-3$ for the vertices in that order. The outcome of this construction is that $V_1$ through $V_{n-3}$ get deleted in that order. To see this, when $V_i$ is deleted, the degree of $V_{i+1}$ stays the same while the degrees of all other vertices decrease, and $V_{i+1}$ becomes the new unique highest degree, as in all previous moves, the degree of all other vertices decreases but it had a non-decreasing move. remark: this problem is just a construction, but there is a lot more behind the scenes for motivation. First of all, the idea is that to achieve $n-3$, all but one of the degrees $2,3,\dots n-1$ must be deleted. However, a post-removal graph cannot contain a universal vertex, since there is no way for the just-deleted vertex to be strictly higher than that. Thus, using "circular optimization", it is actually guaranteed that a construction without a universal vertex exists, since otherwise it is not possible to achieve the bound for $n+1$ as we still need an optimal graph after the deletion. Knowing that every degree from $2$ to $n-2$ is hit helps narrow down our search significantly.