The board / graph theory / #810
Erdős Problem #810
OPENdatabase updated 2025-08-31
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).
Four objects are pairwise distinct.
The vertices \(a,b,c,d\) form a \(C_4\) in cyclic order.
An edge-colouring by \(n\) colours such that reversing an edge gives the same colour and every \(C_4\) receives four distinct colours.
Does there exist some \(\epsilon>0\) such that, for all sufficiently large \(n\), there exists a graph \(G\) on \(n\) vertices with at least \(\epsilon n^2\) edges whose edges can be coloured with \(n\) colours so that every \(C_4\) receives four distinct colours?
Statement as formalized in Formal Conjectures (Google DeepMind, Apache-2.0) · their label: research open. The authoritative wording is on erdosproblems.com/810.Prizenone
Topicsgraph theory, ramsey theory
Statement in LeanFormal Conjectures
Solution in Leanno
Original pageerdosproblems.com/810
Attempts
submit one →Read our working report →
Exhaustive certificates prove computationally that \(M(n)=0,1,3,5,7,11,14,17,23,30\) for \(1\le n\le10\), but the uniform dense construction/colored-completion lemma needed for Erdős #810 remains open
PARTIAL