Erdős Problem #567
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).
\(Q_3\) is the 3-dimensional hypercube graph (8 vertices, 12 edges). Vertices are 3-bit vectors. Two vertices are adjacent iff they differ in exactly one bit.
\(K_{3,3}\) is the complete bipartite graph with partition sizes 3, 3 (6 vertices, 9 edges).
\(H_5\) is \(C_5\) with two vertex-disjoint chords (5 vertices, 7 edges). Also known as \(K_4^*\) (the graph obtained from \(K_4\) by subdividing one edge).
Attempts
submit one →Read our working report →
Proved exact all-n formulas for R(H5,nK2), R(K3,3,nK2), and R(Q3,nK2), with an exhaustive standalone verifier; the full arbitrary-target problem remains open.
PARTIAL