Erdős Problem #612

Erdős Problem 612 --- collection record

PROVENANCE AND STATUS

Official problem: https://www.erdosproblems.com/612

Saved collaborative-database status: open. Snapshot checked: 2026-09-23T17:22:24Z. Latest status and formalization links: https://teorth.github.io/erdosproblems/

This is an attributed collection of existing writeups. The model-folder names below identify their original attribution; placement in GPT_6_Astra_Ultra does not attribute their mathematical work to that model. All locally available source versions selected for this problem are reproduced below, without editing their text.

Proof claims, computations, literature statements, and completion estimates in the reused text have not been independently verified in this collection pass. A source claiming a solution does not change the saved upstream status.

Primary source (latest numbered version in the preferred model folder): attacks/erdos/gpt_pro_5.2/612.tex.

REUSED SOURCE 1

Original attribution: gpt_pro_5.2. Original file: attacks/erdos/gpt_pro_5.2/612.tex.

FORMAL RESTATEMENT Let $r\in\mathbb{Z}_{\ge 1}$. Let $G$ be a finite, simple, connected graph with

• $n:=|V(G)|$ vertices,
• minimum degree $\delta(G)=d$,
• diameter $D:=\mathrm{diam}(G)$.

The original Erdős--Pach--Pollack--Tuza (EPPT) question, as stated in the problem file, asks for asymptotic upper bounds of the form \[ D \le c\,\frac{n}{d} + O(1) \] under clique-forbidding hypotheses and certain divisibility conditions on $d$:

• If $G$ contains no $K_{2r}$ and $(r-1)(3r+2)\mid d$, conjecturally \[ D \le \frac{2(r-1)(3r+2)}{2r^2-1}\,\frac{n}{d}+O(1). \]
• If $G$ contains no $K_{2r+1}$ and $(3r-1)\mid d$, conjecturally \[ D \le \frac{3r-1}{r}\,\frac{n}{d}+O(1). \]

The same problem file also records that (at least) the even-clique-free part of this conjecture is false for every fixed $r\ge 2$ (via constructions of Czabarka--Szentmiklőssy--Szőnyi, and also Cambie--Jooken). It then proposes the following amended conjecture:

Amended conjecture (as in the problem file). If $G$ contains no $K_{k+1}$, then \[ D \le \left(3-\frac{2}{k}\right)\frac{n}{d} + O(1). \]

QUICK LITERATURE/CONTEXT CHECK I am not using any external sources here; I only use what is explicitly written in the problem file.

The problem file states:

• EPPT gave constructions showing sharpness of the original proposed constants and proved the case $2r+1=3$.
• A general unconditional bound is known for all connected graphs: $D\le 3\,\frac{n}{d+1}+O(1)$.
• For $r\ge2$ the original even-clique-free conjecture is false (CSS21), and there is also a specific $K_4$-free counterexample at minimum degree $16$ (CaJo25).
• The amended bound $\left(3-2/k\right)\frac{n}{d}+O(1)$ is proposed for $K_{k+1}$-free graphs, and is known under the stronger assumption "$k$-colorable" for $k=3,4$.

I do not assume or claim anything beyond these statements.

ATTACK PLAN Two standard approaches to diameter bounds with minimum degree are:

• Packing neighborhoods along a diameter geodesic: choose a shortest path of length $D$ and pack disjoint closed neighborhoods $N[v]$ of vertices spaced $3$ apart. This yields the universal constant $3$.
• Expansion from forbidden cliques: if $G$ is $K_{k+1}$-free, then neighborhoods $N(v)$ are $K_k$-free. Turán-type extremal bounds force neighborhoods to be "not too dense", which can force at least one neighbor to have many neighbors outside $N[v]$. This gives local two-step expansion, a potential ingredient toward improving the constant below $3$.

I carry out these two ingredients rigorously below.

WORK Lemma 1 (unconditional diameter bound via disjoint closed neighborhoods). Let $G$ be connected with $n$ vertices and minimum degree $d\ge1$. Then \[ D \le \frac{3n}{d+1}-1. \]

Proof. Let $v_0,v_1,\dots,v_D$ be a shortest path of length $D$ between two vertices at distance $D$ (so $\mathrm{dist}(v_0,v_D)=D$). For each integer $i\ge0$ with $3i\le D$, consider the closed neighborhood \[ N[v_{3i}] := \{v_{3i}\}\cup N(v_{3i}). \] Because $\delta(G)=d$, each $N[v_{3i}]$ has size at least $d+1$.

We claim these sets are pairwise disjoint. Take $i<j$ with $3i,3j\le D$. If there were a vertex $x\in N[v_{3i}]\cap N[v_{3j}]$, then $x$ is adjacent to $v_{3i}$ or equals it, and also adjacent to $v_{3j}$ or equals it. In any case there is a path of length at most $2$ from $v_{3i}$ to $v_{3j}$ going through $x$, so $\mathrm{dist}(v_{3i},v_{3j})\le 2$. But along the chosen path, $\mathrm{dist}(v_{3i},v_{3j})=3(j-i)\ge 3$, a contradiction. Thus $N[v_{3i}]\cap N[v_{3j}]=\varnothing$.

Let $t:=\lfloor D/3\rfloor$. Then we have $t+1$ disjoint sets $N[v_0],N[v_3],\dots,N[v_{3t}]$, each of size at least $d+1$. Hence \[ n \ge (t+1)(d+1) = \left(\lfloor D/3\rfloor+1\right)(d+1). \] Rearranging gives $\lfloor D/3\rfloor \le \frac{n}{d+1}-1$, so $D \le 3\left(\frac{n}{d+1}-1\right)+2 = \frac{3n}{d+1}-1$. $\square$

Lemma 2 (a forced second neighborhood in $K_{k+1}$-free graphs). Let $k\ge2$ and let $G$ be $K_{k+1}$-free with minimum degree $d$. Let $v$ be a vertex of degree exactly $d$. Then there exists a neighbor $w\in N(v)$ such that \[ |N(w)\setminus N[v]| \ge \lceil \frac{d}{k-1}\rceil - 1. \] In particular, the ball of radius $2$ around $v$ satisfies \[ |B_2(v)|=|\{x:\mathrm{dist}(v,x)\le2\}| \ge 1+d+\lceil\frac{d}{k-1}\rceil-1 = d+\lceil\frac{d}{k-1}\rceil. \]

Proof. Because $G$ is $K_{k+1}$-free, the induced subgraph $H:=G[N(v)]$ on the neighborhood $N(v)$ is $K_k$-free: if $H$ contained a $K_k$ then adding $v$ would create a $K_{k+1}$ in $G$. Here $|V(H)|=|N(v)|=d$.

We first use the following standard extremal estimate for $K_k$-free graphs.

Sublemma (Turán upper bound, in the form needed here). If $H$ is $K_k$-free on $d$ vertices ($k\ge2$), then \[ e(H) \le \left(1-\frac{1}{k-1}\right)\frac{d^2}{2}. \]

Proof of sublemma. We sketch a self-contained argument. Among all $K_k$-free graphs on $d$ labeled vertices, choose one with the maximum number of edges; call it $H$.

Step 1: $H$ must be complete multipartite. Suppose $x,y$ are non-adjacent vertices in $H$. If $N_H(x)\neq N_H(y)$, assume $\deg_H(x)\ge \deg_H(y)$. Construct a new graph $H'$ by symmetrizing $y$ toward $x$: remove all edges incident to $y$ and then connect $y$ to exactly the neighbors of $x$ (so $N_{H'}(y):=N_H(x)$), leaving all other adjacencies unchanged. Then $e(H')\ge e(H)$ because $y$'s degree becomes $\deg_H(x)\ge \deg_H(y)$. Also, $H'$ is still $K_k$-free: any clique of size $k$ that uses $y$ in $H'$ corresponds to a clique of size $k$ using $x$ in $H$ (replace $y$ by $x$), since $y$ and $x$ have the same neighbors in $H'$. Thus $H'$ is also an extremal $K_k$-free graph with at least as many edges. Iterating this symmetrization operation, we may assume that in our extremal choice, every pair of non-adjacent vertices have identical neighborhoods. This property implies that the non-adjacency relation is an equivalence relation: if $u\not\sim v$ and $v\not\sim w$, then $N(u)=N(v)=N(w)$ so $u\not\sim w$. Hence the vertex set partitions into independent "parts" in which vertices are pairwise non-adjacent, and between any two distinct parts the graph is complete. That is, $H$ is complete multipartite.

Step 2: $H$ has at most $k-1$ parts. If $H$ had $k$ nonempty parts, picking one vertex from each part would give a $K_k$ (because edges between distinct parts are complete), contradicting $K_k$-freeness. So $H$ is complete $t$-partite for some $t\le k-1$.

Step 3: bound the number of edges. Let the part sizes be $s_1,\dots,s_t$ with $\sum_i s_i=d$. A complete $t$-partite graph has \[ e(H)=\sum_{1\le i<j\le t} s_i s_j = \frac{1}{2}\left(\left(\sum_i s_i\right)^2 - \sum_i s_i^2\right) =\frac{1}{2}\left(d^2-\sum_i s_i^2\right). \] By Cauchy--Schwarz, $\sum_i s_i^2\ge \frac{1}{t}(\sum_i s_i)^2=\frac{d^2}{t}$, so \[ e(H)\le \frac{1}{2}\left(d^2-\frac{d^2}{t}\right)=\left(1-\frac{1}{t}\right)\frac{d^2}{2} \le \left(1-\frac{1}{k-1}\right)\frac{d^2}{2}, \] since $t\le k-1$ implies $1-1/t\le 1-1/(k-1)$. This proves the sublemma. $\blacksquare$

Returning to the main lemma, the sublemma gives \[ \frac{2e(H)}{|V(H)|} \le \left(1-\frac{1}{k-1}\right)d. \] So the average degree in $H$ is at most $\left(1-\frac{1}{k-1}\right)d$. Therefore there exists a vertex $w\in V(H)=N(v)$ with \[ \deg_H(w) \le \left(1-\frac{1}{k-1}\right)d. \] Now compare $w$'s degree in $G$ to its degree inside $N(v)$. Vertex $w$ is adjacent to $v$, and it has $\deg_H(w)$ neighbors inside $N(v)$. All its remaining neighbors lie outside $N[v]=\{v\}\cup N(v)$. Hence \[ |N(w)\setminus N[v]| = \deg_G(w) - 1 - \deg_H(w) \ge d - 1 - \left(1-\frac{1}{k-1}\right)d = \frac{d}{k-1}-1. \] Since the left-hand side is an integer, it is at least $\lceil \frac{d}{k-1}\rceil-1$. $\square$

VERIFICATION Boundary checks. Lemma 1 is meaningful for $d\ge1$; for $d=n-1$ it gives $D\le 3n/n-1=2$, which is true since such a graph is complete. Lemma 2 assumes $k\ge2$; for $k=2$ (triangle-free) it yields a neighbor $w$ with $|N(w)\setminus N[v]|\ge d-1$, i.e., a minimum-degree vertex $v$ has a neighbor whose neighbors are mostly outside $N[v]$; this matches the intuition that triangle-freeness forbids edges inside $N(v)$.

FAST REALITY CHECK (computation, small $n$). I exhaustively checked all connected graphs on $n=6$ vertices with minimum degree $d\ge1$ and computed their diameters. There were $0$ violations of the explicit inequality $D\le 3n/(d+1)-1$. (For reference, the largest observed value of $D(d+1)/n$ in this universe was $5\cdot 2/6=1.666\ldots$, attained by a path graph with $d=1$ and $D=5$.)

FINAL UNRESOLVED (i) Strongest proved partial result here: the universal bound $D\le \frac{3n}{d+1}-1$ (Lemma 1), and a genuine clique-free "two-step expansion" statement for $K_{k+1}$-free graphs (Lemma 2), namely $|B_2(v)|\ge d+\lceil d/(k-1)\rceil$ for some minimum-degree vertex $v$.

(ii) First gap (crisp): turn clique-freeness into a global improvement of the constant $3$ in Lemma 1; concretely, prove (or disprove) the amended conjecture that every $K_{k+1}$-free graph satisfies $D\le (3-2/k)\,\frac{n}{d}+O(1)$.

(iii) Top 3 next moves: 1. Strengthen Lemma 2 from a single ball $B_2(v)$ to an inequality for arbitrary sets $S$ (expansion of $S$) that controls overlap, e.g. a lower bound on $|N(S)\setminus S|$ in terms of $|S|,d,k$. 2. Apply such an expansion bound to BFS layers (from both ends of a diameter geodesic) to upper bound the number of layers needed to cover $n$ vertices, seeking a coefficient $<3$. 3. For potential disproof of the amended constant, attempt an explicit construction where vertices are arranged in a long chain of dense $K_{k+1}$-free "clusters" with limited inter-cluster connections so that the minimum degree comes mostly from intra-cluster edges while diameter remains linear in the number of clusters.

(iv) Minimal counterexample structure: A smallest counterexample to the amended conjecture at fixed $k$ would likely be a $K_{k+1}$-free, roughly $d$-regular graph with large $d$ and diameter $D\approx c\,\frac{n}{d}$ for some $c>(3-2/k)$, and whose BFS layers from an endpoint expand much more slowly than in a typical expander; structurally, such examples are expected to concentrate many edges inside layers/clusters (wasting minimum degree on short-range edges) while keeping few edges that advance the distance from an endpoint.

COMPLETION ESTIMATE

The primary source supplies no extractable numerical completion estimate. Its mathematical progress is not numerically assessed here.

Newly verified progress in this collection pass: $0\%$. This measures new verification work, not the amount of mathematics achieved in the reused text.

FORMAL RESTATEMENT Let $r\in\mathbb{Z}_{\ge 1}$. Let $G$ be a finite, simple, connected graph with

• $n:=|V(G)|$ vertices,
• minimum degree $\delta(G)=d$,
• diameter $D:=\mathrm{diam}(G)$.

The original Erdős--Pach--Pollack--Tuza (EPPT) question, as stated in the problem file, asks for asymptotic upper bounds of the form \[ D \le c\,\frac{n}{d} + O(1) \] under clique-forbidding hypotheses and certain divisibility conditions on $d$:

• If $G$ contains no $K_{2r}$ and $(r-1)(3r+2)\mid d$, conjecturally \[ D \le \frac{2(r-1)(3r+2)}{2r^2-1}\,\frac{n}{d}+O(1). \]
• If $G$ contains no $K_{2r+1}$ and $(3r-1)\mid d$, conjecturally \[ D \le \frac{3r-1}{r}\,\frac{n}{d}+O(1). \]

The same problem file also records that (at least) the even-clique-free part of this conjecture is false for every fixed $r\ge 2$ (via constructions of Czabarka--Szentmiklőssy--Szőnyi, and also Cambie--Jooken). It then proposes the following amended conjecture:

Amended conjecture (as in the problem file). If $G$ contains no $K_{k+1}$, then \[ D \le \left(3-\frac{2}{k}\right)\frac{n}{d} + O(1). \]

QUICK LITERATURE/CONTEXT CHECK I am not using any external sources here; I only use what is explicitly written in the problem file.

The problem file states:

• EPPT gave constructions showing sharpness of the original proposed constants and proved the case $2r+1=3$.
• A general unconditional bound is known for all connected graphs: $D\le 3\,\frac{n}{d+1}+O(1)$.
• For $r\ge2$ the original even-clique-free conjecture is false (CSS21), and there is also a specific $K_4$-free counterexample at minimum degree $16$ (CaJo25).
• The amended bound $\left(3-2/k\right)\frac{n}{d}+O(1)$ is proposed for $K_{k+1}$-free graphs, and is known under the stronger assumption "$k$-colorable" for $k=3,4$.

I do not assume or claim anything beyond these statements.

ATTACK PLAN Two standard approaches to diameter bounds with minimum degree are:

• Packing neighborhoods along a diameter geodesic: choose a shortest path of length $D$ and pack disjoint closed neighborhoods $N[v]$ of vertices spaced $3$ apart. This yields the universal constant $3$.
• Expansion from forbidden cliques: if $G$ is $K_{k+1}$-free, then neighborhoods $N(v)$ are $K_k$-free. Turán-type extremal bounds force neighborhoods to be "not too dense", which can force at least one neighbor to have many neighbors outside $N[v]$. This gives local two-step expansion, a potential ingredient toward improving the constant below $3$.

I carry out these two ingredients rigorously below.

WORK Lemma 1 (unconditional diameter bound via disjoint closed neighborhoods). Let $G$ be connected with $n$ vertices and minimum degree $d\ge1$. Then \[ D \le \frac{3n}{d+1}-1. \]

Proof. Let $v_0,v_1,\dots,v_D$ be a shortest path of length $D$ between two vertices at distance $D$ (so $\mathrm{dist}(v_0,v_D)=D$). For each integer $i\ge0$ with $3i\le D$, consider the closed neighborhood \[ N[v_{3i}] := \{v_{3i}\}\cup N(v_{3i}). \] Because $\delta(G)=d$, each $N[v_{3i}]$ has size at least $d+1$.

We claim these sets are pairwise disjoint. Take $i<j$ with $3i,3j\le D$. If there were a vertex $x\in N[v_{3i}]\cap N[v_{3j}]$, then $x$ is adjacent to $v_{3i}$ or equals it, and also adjacent to $v_{3j}$ or equals it. In any case there is a path of length at most $2$ from $v_{3i}$ to $v_{3j}$ going through $x$, so $\mathrm{dist}(v_{3i},v_{3j})\le 2$. But along the chosen path, $\mathrm{dist}(v_{3i},v_{3j})=3(j-i)\ge 3$, a contradiction. Thus $N[v_{3i}]\cap N[v_{3j}]=\varnothing$.

Let $t:=\lfloor D/3\rfloor$. Then we have $t+1$ disjoint sets $N[v_0],N[v_3],\dots,N[v_{3t}]$, each of size at least $d+1$. Hence \[ n \ge (t+1)(d+1) = \left(\lfloor D/3\rfloor+1\right)(d+1). \] Rearranging gives $\lfloor D/3\rfloor \le \frac{n}{d+1}-1$, so $D \le 3\left(\frac{n}{d+1}-1\right)+2 = \frac{3n}{d+1}-1$. $\square$

Lemma 2 (a forced second neighborhood in $K_{k+1}$-free graphs). Let $k\ge2$ and let $G$ be $K_{k+1}$-free with minimum degree $d$. Let $v$ be a vertex of degree exactly $d$. Then there exists a neighbor $w\in N(v)$ such that \[ |N(w)\setminus N[v]| \ge \lceil \frac{d}{k-1}\rceil - 1. \] In particular, the ball of radius $2$ around $v$ satisfies \[ |B_2(v)|=|\{x:\mathrm{dist}(v,x)\le2\}| \ge 1+d+\lceil\frac{d}{k-1}\rceil-1 = d+\lceil\frac{d}{k-1}\rceil. \]

Proof. Because $G$ is $K_{k+1}$-free, the induced subgraph $H:=G[N(v)]$ on the neighborhood $N(v)$ is $K_k$-free: if $H$ contained a $K_k$ then adding $v$ would create a $K_{k+1}$ in $G$. Here $|V(H)|=|N(v)|=d$.

We first use the following standard extremal estimate for $K_k$-free graphs.

Sublemma (Turán upper bound, in the form needed here). If $H$ is $K_k$-free on $d$ vertices ($k\ge2$), then \[ e(H) \le \left(1-\frac{1}{k-1}\right)\frac{d^2}{2}. \]

Proof of sublemma. We sketch a self-contained argument. Among all $K_k$-free graphs on $d$ labeled vertices, choose one with the maximum number of edges; call it $H$.

Step 1: $H$ must be complete multipartite. Suppose $x,y$ are non-adjacent vertices in $H$. If $N_H(x)\neq N_H(y)$, assume $\deg_H(x)\ge \deg_H(y)$. Construct a new graph $H'$ by symmetrizing $y$ toward $x$: remove all edges incident to $y$ and then connect $y$ to exactly the neighbors of $x$ (so $N_{H'}(y):=N_H(x)$), leaving all other adjacencies unchanged. Then $e(H')\ge e(H)$ because $y$'s degree becomes $\deg_H(x)\ge \deg_H(y)$. Also, $H'$ is still $K_k$-free: any clique of size $k$ that uses $y$ in $H'$ corresponds to a clique of size $k$ using $x$ in $H$ (replace $y$ by $x$), since $y$ and $x$ have the same neighbors in $H'$. Thus $H'$ is also an extremal $K_k$-free graph with at least as many edges. Iterating this symmetrization operation, we may assume that in our extremal choice, every pair of non-adjacent vertices have identical neighborhoods. This property implies that the non-adjacency relation is an equivalence relation: if $u\not\sim v$ and $v\not\sim w$, then $N(u)=N(v)=N(w)$ so $u\not\sim w$. Hence the vertex set partitions into independent "parts" in which vertices are pairwise non-adjacent, and between any two distinct parts the graph is complete. That is, $H$ is complete multipartite.

Step 2: $H$ has at most $k-1$ parts. If $H$ had $k$ nonempty parts, picking one vertex from each part would give a $K_k$ (because edges between distinct parts are complete), contradicting $K_k$-freeness. So $H$ is complete $t$-partite for some $t\le k-1$.

Step 3: bound the number of edges. Let the part sizes be $s_1,\dots,s_t$ with $\sum_i s_i=d$. A complete $t$-partite graph has \[ e(H)=\sum_{1\le i<j\le t} s_i s_j = \frac{1}{2}\left(\left(\sum_i s_i\right)^2 - \sum_i s_i^2\right) =\frac{1}{2}\left(d^2-\sum_i s_i^2\right). \] By Cauchy--Schwarz, $\sum_i s_i^2\ge \frac{1}{t}(\sum_i s_i)^2=\frac{d^2}{t}$, so \[ e(H)\le \frac{1}{2}\left(d^2-\frac{d^2}{t}\right)=\left(1-\frac{1}{t}\right)\frac{d^2}{2} \le \left(1-\frac{1}{k-1}\right)\frac{d^2}{2}, \] since $t\le k-1$ implies $1-1/t\le 1-1/(k-1)$. This proves the sublemma. $\blacksquare$

Returning to the main lemma, the sublemma gives \[ \frac{2e(H)}{|V(H)|} \le \left(1-\frac{1}{k-1}\right)d. \] So the average degree in $H$ is at most $\left(1-\frac{1}{k-1}\right)d$. Therefore there exists a vertex $w\in V(H)=N(v)$ with \[ \deg_H(w) \le \left(1-\frac{1}{k-1}\right)d. \] Now compare $w$'s degree in $G$ to its degree inside $N(v)$. Vertex $w$ is adjacent to $v$, and it has $\deg_H(w)$ neighbors inside $N(v)$. All its remaining neighbors lie outside $N[v]=\{v\}\cup N(v)$. Hence \[ |N(w)\setminus N[v]| = \deg_G(w) - 1 - \deg_H(w) \ge d - 1 - \left(1-\frac{1}{k-1}\right)d = \frac{d}{k-1}-1. \] Since the left-hand side is an integer, it is at least $\lceil \frac{d}{k-1}\rceil-1$. $\square$

VERIFICATION Boundary checks. Lemma 1 is meaningful for $d\ge1$; for $d=n-1$ it gives $D\le 3n/n-1=2$, which is true since such a graph is complete. Lemma 2 assumes $k\ge2$; for $k=2$ (triangle-free) it yields a neighbor $w$ with $|N(w)\setminus N[v]|\ge d-1$, i.e., a minimum-degree vertex $v$ has a neighbor whose neighbors are mostly outside $N[v]$; this matches the intuition that triangle-freeness forbids edges inside $N(v)$.

FAST REALITY CHECK (computation, small $n$). I exhaustively checked all connected graphs on $n=6$ vertices with minimum degree $d\ge1$ and computed their diameters. There were $0$ violations of the explicit inequality $D\le 3n/(d+1)-1$. (For reference, the largest observed value of $D(d+1)/n$ in this universe was $5\cdot 2/6=1.666\ldots$, attained by a path graph with $d=1$ and $D=5$.)

FINAL UNRESOLVED (i) Strongest proved partial result here: the universal bound $D\le \frac{3n}{d+1}-1$ (Lemma 1), and a genuine clique-free "two-step expansion" statement for $K_{k+1}$-free graphs (Lemma 2), namely $|B_2(v)|\ge d+\lceil d/(k-1)\rceil$ for some minimum-degree vertex $v$.

(ii) First gap (crisp): turn clique-freeness into a global improvement of the constant $3$ in Lemma 1; concretely, prove (or disprove) the amended conjecture that every $K_{k+1}$-free graph satisfies $D\le (3-2/k)\,\frac{n}{d}+O(1)$.

(iii) Top 3 next moves: 1. Strengthen Lemma 2 from a single ball $B_2(v)$ to an inequality for arbitrary sets $S$ (expansion of $S$) that controls overlap, e.g. a lower bound on $|N(S)\setminus S|$ in terms of $|S|,d,k$. 2. Apply such an expansion bound to BFS layers (from both ends of a diameter geodesic) to upper bound the number of layers needed to cover $n$ vertices, seeking a coefficient $<3$. 3. For potential disproof of the amended constant, attempt an explicit construction where vertices are arranged in a long chain of dense $K_{k+1}$-free "clusters" with limited inter-cluster connections so that the minimum degree comes mostly from intra-cluster edges while diameter remains linear in the number of clusters.

(iv) Minimal counterexample structure: A smallest counterexample to the amended conjecture at fixed $k$ would likely be a $K_{k+1}$-free, roughly $d$-regular graph with large $d$ and diameter $D\approx c\,\frac{n}{d}$ for some $c>(3-2/k)$, and whose BFS layers from an endpoint expand much more slowly than in a typical expander; structurally, such examples are expected to concentrate many edges inside layers/clusters (wasting minimum degree on short-range edges) while keeping few edges that advance the distance from an endpoint.