Status
On this page
Status
Topics
Status
On this page
Status
Topics
If is a graph on vertices which contains no trivial (empty or complete) subgraph on many vertices, then must contain an induced non-trivial regular subgraph on many vertices?
Source: erdosproblems.com/1031
An accepted solution exists. The statement is true.
Proved. The site credits Prömel and Rödl [PrRo99], whose theorem is stronger than the question: for every , a graph on vertices with no trivial subgraph on vertices contains every graph on vertices as an induced subgraph, among them a cycle, which is regular and non-trivial. The paper (J. Combin. Theory Ser. A 88 (1999), 379--384; refereed) is not held; its statement is known through its signed zbMATH review and the site, and the claim page Prömel and Rödl records it as accepted on the refereed venue and the curator's acceptance after the forum comment of 13 September 2025, with the zbMATH review as the source of the statement's wording; the proof-claim tab is empty and nothing is independently reviewed here.