Erdős Problem #85

declared status 'open'. Formalized: yes. Let $n\geq 4$ and $f(n)$ be minimal such that every graph on $n$ vertices with minimal degree $\geq f(n)$ contains a $C_4$. Is it true that, for all large $n$, $f(n+1)\geq f(n)$? Current best: The function $f(n)$ is a reformulation of the Ramsey number $R(C_4,K_{1,n})$, in that$$R(C_4,K_{1,n})=\min\{ m : f(m)\leq m-n\}$$and$$f(n)=\min\{ m : m\geq R(C_4, K_{1,n-m})\}.$$The behaviour of this Ramsey number more generally is [552]. Prize: no. OEIS: A006672. Tags: graph theory.

Notation is rendered from the stored source. The pinned checkout remains the exact record.