Iranian Mathematical Olympiad

First, we make an example. Assume these vertices
$$\begin{array}{ccccccccccc} u & u & m & m & \dots & m & m & m & m \\ m & m & u & u & \dots & m & m & m & m \\ \vdots & \vdots & \vdots & \vdots & \ddots & \vdots & \vdots & \vdots & \vdots & 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. ■