Problem 73

../

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

---

Statement. Let $k\geq 0$. Let $G$ be a graph such that every subgraph $H$ contains an independent set of size $\geq (n-k)/2$, where $n$ is the number of vertices of $H$. Must $G$ be the union of a bipartite graph and $O_k(1)$ many vertices?

Status. Proved: the site labels the problem PROVED and credits Reed [Re99], noting with him that the case $k=0$ is trivial. The frontmatter standing is derived from the one claim page under claims/, Reed, accepted on the refereed publication and the site's credit.

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

References.

• [Re99] Reed, B., Mangoes and Blueberries. Combinatorica 19 (1999), no. 2, 267-296.

Formalization. Statement in formal-conjectures.

Progress

Not yet compiled.

Known Results

Not yet compiled.