Problem 1037

../

claims/: The 1 claim page of Problem 1037, one per claimant's result; the problem's standing derives from them.

---

Statement. Let $G$ be a graph on $n$ vertices in which every degree occurs at most twice, and the number of distinct degree is $>(\frac{1}{2}+\epsilon)n$. Must $G$ contain a trivial (empty or complete) subgraph of size 'much larger' than $\log n$?

Formulation. The site's wording (page last edited 5 March 2026); its "distinct degree" is a misprint for "distinct degrees", the word of Erdős's source. The phrase 'much larger' than $\log n$ is read as the site's curator, Thomas Bloom, read it in the thread on 19 January 2026, and as the formal statement ErdosProblems/1037.lean at the pinned commit encodes it: for every $\epsilon>0$ and every $C>0$, for all sufficiently large $n$, every graph on $n$ vertices in which every degree occurs at most twice and which has more than $(\frac12+\epsilon)n$ distinct degrees has a trivial subgraph on more than $C\log n$ vertices. The curator's sentence leaves out the at-most-twice hypothesis, which the formal statement keeps. The construction on the claim page refutes this reading for every $\epsilon<\frac14$. Erdős's source, [Er93] p. 347 (card), also asks the question with more than $(\frac23+\epsilon)n$ distinct degrees, which the site's statement omits; the same construction answers it no for every $\epsilon<\frac1{12}$.

Status. DISPROVED (LEAN), the site's label. The claim page (Cambie, Chan and Hunter) records the construction the site credits, with the Lean formalization of it in Boris Alexeev's repository linked from that page; the formalization was not built or audited here, and the standing rests on the site's acceptance.

Source. erdosproblems.com/1037, accessed 2026-09-04. Cite as: T. F. Bloom, Erdős Problem #1037, https://www.erdosproblems.com/1037.

Formalization. Statement in formal-conjectures.

Progress

Not yet compiled.

Known Results

Not yet compiled.