Iranian Mathematical Olympiad

First, we make an example. Assume these vertices $$\begin{array}{cccccccccc}u& u& m& m& \dots & m& m& m& m& \\ m& m& u& u& \dots & m& m& m& m& \\ ⋮& ⋮& ⋮& ⋮& \ddots & ⋮& ⋮& ⋮& ⋮& m\\ m& m& m& m& \dots & u& u& w& m& \\ m& m& m& m& \dots & m& m& u& u& \\ m& m& m& m& \dots & m& m& m& m& \end{array}$$ where $m$'s are marked vertices and $u$'s are unmarked vertices. (in case of odd $n$ two vertices have an $m$ in common) If we initially mark them, then after one minute all vertices with one $m$ will be marked. So after two minutes all vertices with two $m$s will be marked, and so on. So after $n$ minutes all vertices will be marked.

Now we have to prove that if we initially mark $k$ vertices, and after a while all vertices get marked, then $k\ge \lfloor \frac{n}{2}\rfloor +1$.

Consider the connected components of marked vertices every minute. We claim that every marked-connected component with $i$ initially marked vertices has diameter at most $2i-2$. We prove our claim by induction. First step is easy to prove. Now assume that after $t$ minutes, the claim is true. After $t+1$ minutes, if two (or more) marked connected components with $i,j$ initially marked vertices merge, then the diameter of the new merged marked component will be at most $$2i-2+2+2j-2=2(i+j)-2$$ So by this claim, after a while we have one connected component having all vertices. This connected component has $k$ initially marked vertices and diameter $n$. Therefore, we have $n\le 2k-2$ which concludes our bound. ■