MMO Round 4

Answer: If $m = 1$, then the maximum distance is $n-1$. If $m \ge 2$, then the maximum distance is
$$3 \left\lfloor \frac{n}{m+1} \right\rfloor - \varepsilon(n), \quad \text{where } \varepsilon(n) = \begin{cases} 3 & \text{if } n \equiv 0 \pmod{m+1}, \\ 2 & \text{if } n \equiv 1 \pmod{m+1}, \\ 1 & \text{otherwise.} \end{cases}$$
Proof: Model the situation as a connected graph $G$ with $n$ vertices, where each vertex has degree at least $m$. Let $d$ be the maximum distance between any two vertices. Let $P = v_0, v_1, \dots, v_d$ be a path of length $d$ in a connected component $G'$ of $G$.
For each $0 \le i \le d$, define the set
$$V_i = \{u \in G' \mid \text{the distance from } u \text{ to } v_0 \text{ is } i\}.$$
Then $G' = \bigsqcup_{i=0}^d V_i$ (disjoint union). And let $V_{-1} = V_{n+1} = \emptyset$. By the triangle inequality, any neighbor of a vertex in $V_i$ lies in $V_{i-1} \cup V_i \cup V_{i+1}$. Since each vertex has at least $m$ neighbors, we obtain the inequality
$$|V_{i-1} \cup V_i \cup V_{i+1}| \ge m + 1.$$
Let $h = \left\lfloor \frac{n}{m+1} \right\rfloor$. We now show that $d \le 3h - \varepsilon(n)$.
This is done by considering the three residue cases of $n \pmod{(m+1)}$ and showing that any longer path would require more than $n$ vertices, leading to a contradiction in each case.

Case 1: $n \equiv 0 \pmod{m+1}$.
Let $n = h(m+1)$. Assume that $d \ge 3h-2$. Then the number of vertices in the path satisfies:
$$\begin{aligned} n &\ge |V_0 \cup V_1| + |V_2| + |V_3 \cup V_4 \cup V_5| + \dots + |V_{3h-3} \cup V_{3h-2}| \\ &\ge (m+1) + 1 + (m+1) + \dots + (m+1) \\ &= 1 + h(m+1) = 1 + n,\end{aligned}$$
a contradiction.

Case 2: $n \equiv 1 \pmod{m+1}$.
Let $n = h(m + 1) + 1$. Assume that $d \ge 3h - 1$. Then:
$$\begin{aligned} n &\ge |V_0 \sqcup V_1| + |V_2| + |V_3| + |V_4 \sqcup V_5 \sqcup V_6| + \dots + |V_{3h-2} \sqcup V_{3h-1}| \\ &\ge (m+1) + 1 + 1 + (m+1) + \dots + (m+1) \\ &= 2 + h(m+1),\end{aligned}$$
again contradicting $n = h(m + 1) + 1$.

Case 3: $n \not\equiv 0, 1 \pmod{m+1}$.
Then $n = h(m + 1) + r$ for some $2 \le r \le m$. Assume that $d \ge 3h$. Then:
$$\begin{aligned} n &\ge |V_0 \sqcup V_1| + |V_2 \sqcup V_3 \sqcup V_4| + \dots + |V_{3h-4} \sqcup V_{3h-3} \sqcup V_{3h-2}| + |V_{3h-1} \sqcup V_{3h}| \\ &\ge (h+1)(m+1),\end{aligned}$$
which implies $n \ge (h+1)(m+1) > h(m+1) + r = n$, again a contradiction.