gpt pro 5.2 attempt on Math-5767

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.