Erdős Problems

Browse all problems

↑ ↓ to move↵ to openesc to close

Loading problem…

Status

On this page

Status

Topics

Terms Privacy info@plasma.ai

Problem 750 — Erdős Problems

Problem 750

Let $f(m)$ be some function such that $f(m)\to \infty$ as $m\to \infty$ . Does there exist a graph $G$ of infinite chromatic number such that every subgraph on $m$ vertices contains an independent set of size at least $\frac{m}{2}-f(m)$ ?

Source: erdosproblems.com/750

Graph theory
Chromatic number

Wiki page

Status

Solved·, Proved

An accepted solution exists. The statement is true.

PROVED (LEAN): a 2026 note by Chojecki with the AI system GPT-5.5 Pro proves the statement; the Lean qualification refers to third-party formalizations, the first assuming Stiebitz's theorem as an axiom and a later one proving it unconditionally, neither among the corpus's audited builds.

EHS82: Erdős, P. and Hajnal, A. and Szemerédi, E., On almost bipartite large chromatic graphs. Theory and practice of combinatorics (1982), 117-123.
Er69b: Erdős, P., Problems and results in chromatic graph theory. Proof Techniques in Graph Theory (Proc. Second Ann Arbor Graph Theory Conf., Ann Arbor, Mich., 1968) (1969), 27-35.
ErHa67b: Erdős, P. and Hajnal, András, On chromatic graphs. Mat. Lapok (1967), 1-4.

Proof claims

Loading proof claims…

Discussion

Loading discussion…

PreviousProblem 749 NextProblem 751

On this page

Statement
Status
References
Proof claims
Discussion

Status: Solved, Proved
Topics: Graph theory
Chromatic number
In the wiki: Wiki page