Problem 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?
Categories:
Graph Theory
Progress
Proved by Reed [Re99]. (Thanks also to Reed for pointing out that the case $k=0$ is trivial, since if $G$ is not bipartite then $G$ contains an odd cycle.)See also [922] and the entry in the graphs problem collection.
Source: erdosproblems.com/73 | Last verified: January 13, 2026