The board / graph theory / #545
Erdős Problem #545
OPENdatabase updated 2025-12-02
No proof or disproof is known, and it isn't known whether a finite computation could settle it.
What the community database records, not our verdict. erdosproblems.com no longer shows statuses (why).
The graph formed by connecting a new vertex (`none`) to \(t\) of the vertices of \(K_n\) (`Fin n`).
Let \(m\) be sufficiently large and let \(G\) be a graph with \(m\) edges and no isolated vertices. Is the Ramsey number \(R(G)\) maximised when \(G\) is 'as complete as possible'? That is, if \(m=\binom{n}{2}+t\) edges with \(0\leq t < n\) then is \[R(G)\leq R(H),\] where \(H\) is the graph formed by connecting a new vertex to \(t\) of the vertices of \(K_n\)? A question of Erdős and Graham. The restriction to sufficiently large \(m\) excludes the small counterexamples recorded on the source page. This problem is #10 in Ramsey Theory in the graphs problem collection.
Statement as formalized in Formal Conjectures (Google DeepMind, Apache-2.0) · their label: research open. The authoritative wording is on erdosproblems.com/545.Prizenone
Topicsgraph theory, ramsey theory
Statement in LeanFormal Conjectures
Solution in Leanno
OEISA059442
Original pageerdosproblems.com/545
Attempts
submit one →Read our working report →
proved from scratch that the eight-edge colex graph has Ramsey number 18 (so its exact matching counterexample gap is 5), and located the missed 1989 theorem \(R(\widehat K_{n,2})=R(K_n)\) for every \
PARTIAL