Erdős Problem #61
Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: open (not automatically the live result).
Subject areas: graph theory.
Read this status correctly
The status above is reproduced from GCL's immutable external-catalogue snapshot. It is not a new claim of current mathematical resolution, a source-semantic review, an independent proof check, or GCL certification. A published proof and a GCL replay are separate events.
The question in plain language
Let \(H\) be a fixed finite simple graph. The Erdős–Hajnal conjecture asks whether there is a constant \(c(H)>0\) such that every \(n\)‑vertex graph with no induced copy of \(H\) contains a clique or independent set of size at least \(n^{c(H)}\).
Erdős and Hajnal introduced the problem in their 1989 paper Ramsey-type theorems. Their exact formulation was slightly disjunctive: for sufficiently large \(n\), every graph either contains \(H\) as an induced subgraph or contains a homogeneous set of size at least \(n^\varepsilon\). Thus the catalogue formulation is equivalent after adjusting the exponent to handle finitely many small graphs.
The general conjecture is still open. Erdős and Hajnal proved the subpolynomial bound
later improved by Bucić, Nguyen, Scott, and Seymour to
Many structured cases are known. Erdős and Hajnal settled graphs \(H\) with at most four vertices. Chudnovsky and Safra proved the bull case with exponent \(1/4\). Chudnovsky, Scott, Seymour, and Spirkl proved the \(C_5\) case. Nguyen, Scott, and Seymour proved the \(P_5\) case in 2026. Alon, Pach, and Solymosi’s substitution theorem then implies the conjecture for every graph on five vertices.
Several six-vertex cases are now known, but these do not constitute a solution for arbitrary \(H\). The appropriate disposition is therefore BOUNDED_TASK_DESIGNED, with the universal theorem explicitly marked PARTIAL.
Six-section mathematical explanation
The exact assertion is
The constant depends on \(H\), but not on \(n\) or \(G\). “No copy of \(H\)” means no induced copy, not merely no ordinary subgraph.
A small example
Take \(G=2K_2\) with
It has no induced \(P_4\): every four-vertex induced subgraph is \(2K_2\), which has only two edges, whereas \(P_4\) has three. Also,
Thus this example attains equality in the elementary \(P_4\)‑free benchmark \(\max\{\alpha(G),\omega(G)\}\ge\sqrt{|V(G)|}\).
The computation was independently enumerated: no induced \(P_4\) was found, and both the maximum clique and maximum independent set have size \(2\).
What is known
A homogeneous set is either a clique or an independent set. Complementation exchanges these two possibilities:
Therefore the conjecture for \(H\) is equivalent to the conjecture for \(\overline H\). This symmetry is used repeatedly in the known case reductions.
The original 1989 result gives, for every fixed \(H\),
whenever \(G\) is \(H\)‑free and \(n\) is sufficiently large.
The later Bucić–Nguyen–Scott–Seymour result replaces this by
Both bounds are superlogarithmic but subpolynomial, so neither proves the conjectured \(n^{c(H)}\) bound.
If \(H_1\) and \(H_2\) satisfy the Erdős–Hajnal property, then substituting \(H_2\) for a vertex of \(H_1\) preserves the property. This reduces the classification problem to prime graphs.
The primary literature now verifies all graphs on at most five vertices through:
- the at-most-four-vertex theorem;
- the bull theorem;
- the \(C_5\) theorem;
- the \(P_5\) theorem;
- complementation and vertex substitution.
This is a finite classification result, not a solution for all finite graphs.
GCL's current state
As of 2026-10-12, the maintained catalogue status is OPEN. GCL source assignment and evidence (source report pending posting). This is an editorial source audit, not GCL proof certification or mathematical acceptance.
Prerequisites are an exact graph-encoding specification, an independently checked graph generator, and a verifier for induced copies and complete/anticomplete pairs.
The protected Lean file is marked formalized in the packet, but its contents were not available for line-by-line inspection in this environment. Therefore no semantic-equivalence claim about the Lean encoding is made.
The original issue contains the authenticated RESULT/1 source report. This is source evidence, not independent mathematical certification or editorial admission.
What remains
Use the explicitly unresolved pair identified by Chudnovsky–Scott–Seymour–Spirkl:
Input: all non-isomorphic graphs \(G\) on at most \(9\) vertices.
Target: test the finite pure-pair assertion
with \(A\cap B=\varnothing\), \(|A|,|B|\ge\lfloor |V(G)|/4\rfloor\), and \(A,B\) either complete or anticomplete.
Method: exhaustive generation of non-isomorphic graphs; exact induced-subgraph tests for \(C_8\) and \(\overline{C_8}\); exact search over unordered vertex pairs \((A,B)\).
Acceptance: a machine-checkable certificate for every graph through order \(9\), including the graph hash, canonical labeling, selected \(A,B\), and adjacency relation.
Falsification: one \(\mathcal H\)‑free graph with no such pair, together with its canonical adjacency matrix and exhaustive certificate.
Stopping rule: stop after all graphs through order \(9\) are certified or the first counterexample is independently reproduced. This is only a bounded certificate and does not imply the asymptotic conjecture.
Sources and claim boundaries
Maintained problem #61; pinned catalogue revision 536408716724a2402bdfa7c1d764bf83d64a8c89.
The pinned catalogue record reports status open, last updated 2025-08-31; that status remains correct for the universal conjecture.
The live page was accessed on 2026-10-12 and was last edited 2026-04-10: Erdős Problems #61. Its newer case list is consistent with the primary literature:
Erdős–Hajnal proved the general bound:
Bucić–Nguyen–Scott–Seymour improved this for every fixed \(H\):
See arXiv:2301.10147, published as IMRN 2024, 9991–10004. - The conjecture is proved for every \(H\) with at most four vertices; for the bull by Chudnovsky–Safra, with the explicit exponent \(1/4\), JCTB 98 (2008), 1301–1310. - Alon–Pach–Solymosi proved closure under vertex substitution, Combinatorica 21 (2001), 155–170. - The \(C_5\) case was proved by Chudnovsky–Scott–Seymour–Spirkl, arXiv:2102.04994, published in PLMS 126 (2023), 997–1014. - Nguyen–Scott–Seymour proved the \(P_5\) case, arXiv:2312.15333, published as PLMS 132 (2026), e70133. Together with substitution closure, this settles every graph \(H\) on five vertices. - Selected six-vertex cases are reported in recent preprints; their proof status is not independently certified here, including the \(E\)‑graph and Bird graph in arXiv:2606.06258, and the graph with edge set \(\{ab,bc,cd,de,af,bf,df\}\) in arXiv:2608.28551.
No cited source proves the statement for arbitrary finite \(H\). The full proof is therefore PARTIAL: the universal conjecture remains open.
Reused evidence: the supplied issue.json, the supplied live.html, the pinned catalogue metadata, and the publicly accessible primary papers linked above. No sibling returns or undisclosed campaign material were inspected. The finite example below was independently enumerated and checked; no independent verification of the long published proofs is claimed.
Catalogue and evidence provenance
- Pinned catalogue source: teorth/erdosproblems at
536408716724. - GCL issue: #1330 — protected issue/assignment identity; its labels and results are live, not reproduced automatically here.
- GCL triage: PROTECTED_READY_BACKLOG.
- Formal-statement coverage: A provider statement was included in the pinned snapshot. Presence does not mean the statement or proof has been checked.
- External mathematical status: consult current problem page and its dated bibliography.