MMO2025 Round 4

Answer: If $m=1$, then the maximum distance is $n-1$. If $m\ge 2$, then the maximum distance is $$3\lfloor \frac{n}{m+1}\rfloor -\epsilon (n),\text{where }\epsilon (n)=\{\begin{array}{ll}3& \text{if }n\equiv 0(\mathrm{mod}m+1),\\ 2& \text{if }n\equiv 1(\mathrm{mod}m+1),\\ 1& \text{otherwise.}\end{array}$$ 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^{\prime }$ of $G$. For each $0\le i\le d$, define the set $$V_i=\{u\in G^{\prime }\mid \text{the distance from }u\text{ to }{v}_0\text{ is }i\}.$$ Then $G^{\prime }={⨆}_{i=0}^d{V}_i$ (disjoint union). And let $V_{-1}=V_{n+1}=\varnothing$. 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=\lfloor \frac{n}{m+1}\rfloor$. We now show that $d\le 3h-\epsilon (n)$. This is done by considering the three residue cases of $n(\mathrm{mod}(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(\mathrm{mod}m+1)$. Let $n=h(m+1)$. Assume that $d\ge 3h-2$. Then the number of vertices in the path satisfies: $$\begin{array}{rl}n& \ge |V_0\cup V_1|+|V_2|+|V_3\cup V_4\cup V_5|+\cdots +|V_{3h-3}\cup V_{3h-2}|\\ & \ge (m+1)+1+(m+1)+\cdots +(m+1)\\ & =1+h(m+1)=1+n,\end{array}$$ a contradiction.

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

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