Loading problem…
Status
On this page
Status
Topics
Problem 73
Let . Let be a graph such that every subgraph contains an independent set of size , where is the number of vertices of . Must be the union of a bipartite graph and many vertices?
Source: erdosproblems.com/73
- Graph theory
Status
Solved, ProvedAn accepted solution exists. The statement is true.
Proved: the site labels the problem PROVED and credits Reed
[Re99], noting with him that the case 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.