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.

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.

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.

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.

$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.

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.