, 1997

a. Starting from the graph $G$, each time we remove a vertex with degree less than $\frac{m}{n}$ together with its edges, until there does not exist such a vertex. Since each time we have removed less than $\frac{m}{n}$ edges, it is impossible that we remove all $n$ vertices since otherwise there is no vertex left but the number of edges is more than $m - n \cdot \frac{m}{n} = 0$. Thus, we must end up with a nonempty set $S$ of vertices such that the degree of each vertex is at least $\left\lfloor \frac{m}{n} \right\rfloor$.

b. Let $T_j$ be the set of vertices in $S$ that has distance $j$ from $v$. Note that the neighbours of a vertex in $T_j$ can only belong to $T_{j-1}$, $T_j$ or $T_{j+1}$.

For $1 \le j \le k$, a vertex in $T_j$ must be adjacent to a vertex in $T_{j-1}$ by the definition of distances. Note that this vertex is uniquely determined. Otherwise, we can form a cycle of length $j + j = 2j \le 2k$, contradicting the assumption.

Also, for $1 \le j \le k-1$, a vertex in $T_j$ cannot be adjacent to another vertex in $T_j$, since otherwise we can form a cycle of length $j+1+j = 2j+1 < 2k$, contradicting the assumption.

It follows that for $1 \le j \le k-1$, each vertex in $T_j$ is adjacent to at least $\frac{m}{n} - 1$ vertices in $T_{j+1}$. By induction, since $|T_0| = 0$, we easily find that
$$|T_j| \ge \left( \frac{m}{n} - 1 \right)^j$$
for $0 \le j \le k$. In particular, we have
$$|T_k| \ge \left[ \left( \frac{m}{n} - 1 \right)^k \right]$$.