# The Erdős–Hajnal conjecture

Every graph on $n$ vertices has a clique or an independent set of size about $\tfrac12\log_2 n$, and random graphs show that one cannot do much better in general. Erdős and Hajnal conjectured that forbidding any single fixed induced subgraph changes this dramatically, forcing a homogeneous set of polynomial size $n^{c}$.

## Problem

A graph $G$ is **$H$-free** if no induced subgraph of $G$ is isomorphic to $H$. Is it true that for every graph $H$ there is a constant $c=c(H)>0$ such that every $H$-free graph on $n$ vertices contains a clique or an independent set with at least $n^{c}$ vertices?

## Background

Erdős and Hajnal stated the conjecture in their 1989 paper "Ramsey-type theorems", where they proved that $H$-free graphs always contain a homogeneous set of size $\exp(c_H\sqrt{\log n})$, far more than the logarithmic size that is guaranteed in general. The conjecture says that excluding one induced subgraph imposes enough structure to push this up to a power of $n$. It has motivated a long series of papers on the structure of graphs with forbidden induced subgraphs.

## What is known

- **General bound.** Erdős and Hajnal (1989) proved the bound $\exp(c_H\sqrt{\log n})$; Bucić, Nguyen, Scott and Seymour (2024) improved it to $\exp(c_H\sqrt{\log n\,\log\log n})$.
- **Small graphs.** The conjecture holds for every $H$ with at most four vertices (Erdős and Hajnal), for the bull (Chudnovsky and Safra, 2008), for the 5-cycle (Chudnovsky, Scott, Seymour and Spirkl, 2023) and for the path on five vertices (Nguyen, Scott and Seymour, 2026). Since Alon, Pach and Solymosi (2001) showed that the class of graphs satisfying the conjecture is closed under vertex substitution, it is now known for all graphs on five vertices. Huang, Ju and Zhou (2026, preprint) added two six-vertex graphs, the E-graph and the bird graph.
- **Paths.** Nguyen, Scott and Seymour showed that for every path $H$, $H$-free graphs have homogeneous sets of size $2^{(\log n)^{1-o(1)}}$. In October 2026 Nguyen posted a proof of the conjecture for every path ([arXiv:2610.24887](https://arxiv.org/abs/2610.24887), preprint), which the source page now cites.

## What would count as progress

- A proof for a further graph $H$ whose case does not follow from the known results, for example another graph on six vertices.
- A general bound of the form $\exp((\log n)^{1/2+\delta})$ for some $\delta>0$ and all $H$.
- Independent checking and simplification of the October 2026 proof for paths.
- A counterexample: a graph $H$ and a family of $H$-free graphs with no homogeneous set of size $n^{\varepsilon}$ for any fixed $\varepsilon>0$; such families can be tested at moderate sizes by computing clique and independence numbers.
- A formal proof against the Lean statement in [formal-conjectures](https://github.com/google-deepmind/formal-conjectures/blob/main/FormalConjectures/ErdosProblems/61.lean).

## References

1. P. Erdős and A. Hajnal, Ramsey-type theorems, *Discrete Appl. Math.* 25 (1989), 37–52. [doi:10.1016/0166-218X(89)90045-0](https://doi.org/10.1016/0166-218X(89)90045-0)
2. N. Alon, J. Pach and J. Solymosi, Ramsey-type theorems with forbidden subgraphs, *Combinatorica* 21 (2001), 155–170. [doi:10.1007/s004930100016](https://doi.org/10.1007/s004930100016)
3. M. Chudnovsky, A. Scott, P. Seymour and S. Spirkl, Erdős–Hajnal for graphs with no 5-hole, *Proc. London Math. Soc.* 126 (2023), 997–1014. [doi:10.1112/plms.12504](https://doi.org/10.1112/plms.12504)
4. M. Bucić, T. Nguyen, A. Scott and P. Seymour, Induced subgraph density. I. A loglog step towards Erdős–Hajnal, *Int. Math. Res. Not.* 2024 (2024), 9991–10004. [doi:10.1093/imrn/rnae065](https://doi.org/10.1093/imrn/rnae065)
5. T. Nguyen, A. Scott and P. Seymour, Induced subgraph density. V. All paths approach Erdős–Hajnal (2023). [arXiv:2307.15032](https://arxiv.org/abs/2307.15032)
6. T. Nguyen, A. Scott and P. Seymour, Induced subgraph density. VII. The five-vertex path, *Proc. London Math. Soc.* 132 (2026). [doi:10.1112/plms.70133](https://doi.org/10.1112/plms.70133)
7. S. Huang, Y. Ju and Y. Zhou, Erdős–Hajnal conjecture beyond five-vertex graphs (2026). [arXiv:2606.06258](https://arxiv.org/abs/2606.06258)
8. T. H. Nguyen, Erdős–Hajnal for excluding paths (2026). [arXiv:2610.24887](https://arxiv.org/abs/2610.24887)

## Source

Imported from [Erdős Problems 61](https://www.erdosproblems.com/61), curated by Thomas Bloom. Open according to the source as of 2026-10-20. The statement above is written in our own words; see the source for the original wording, history and discussion.