Ukrainian National Mathematical Olympiad

We will use the obvious interpretation in the language of graphs, and for convenience, we will move on to graph complements. From now on, every day the vertex of strictly lowest degree will be removed.

It is clear that when 2 vertices remain, nothing else will happen. For $n = 3$ this bound is achieved by connecting two of the three vertices with an edge.

We show that if at some point there were 4 vertices, there will always be at least 3. Indeed, suppose that there were vertices $A$, $B$, $C$, $D$, and first vertex $D$ was removed, and then $C$. Then the vertex $D$ cannot be connected to any of the vertices $A$, $B$. Also note that in a graph of three vertices $A$, $B$, $C$ the vertex $C$ also cannot be connected to any of the vertices $A$, $B$. But then in the graph on these four vertices the degree of $D$ was at least that of $C$, contradiction.

For example, consider the following graph: a chain of vertices $A_1$, $A_2$, $A_3$, ..., $A_n$, where every two adjacent vertices are connected, and in addition $A_{n-2}$ is connected to $A_n$ (fig. 17). It is clear that the vertices will be removed one by one, in order $A_1$, $A_2$, $A_3$, ..., $A_{n-3}$.