Problem Statement
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)$?
Categories:
Graph Theory Ramsey Theory
Progress
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].A weaker version of the conjecture asks for some constant $c$ such that $f(m)>f(n)-c$ for all $m>n$. This question can be asked for other graphs than $C_4$.
The bounds in [552] imply in particular that $f(n)<\sqrt{n}+1$ and\[f(n)=(1+o(1))\sqrt{n}.\]It is easy to check that $f(4)=2$.
Source: erdosproblems.com/85 | Last verified: January 13, 2026