Loading problem…
Status
On this page
Status
Topics
Problem 767
Let be the maximal number of edges possible on a graph with vertices which does not contain a cycle with chords incident to a vertex on the cycle. Is it true that
for sufficiently large?
Source: erdosproblems.com/767
- Graph theory
- Turán numbers
Status
Solved, ProvedAn accepted solution exists. The statement is true.
Proved. The site labels the problem PROVED and credits Jiang [Ji04] (J. Graph Theory 46 (2004), no. 3, 180--182; refereed). The paper is not held; its abstract is known as deposited in the Crossref record: "Given positive integers and , let denote the maximum number of edges of a graph on vertices that does not contain a cycle with chords incident to a vertex on the cycle. Bollobás conjectured as an exercise in [2, p. 398, Problem 13] that there exists a function such that for all . Using an old result of Bondy [3], we prove the conjecture, showing that ." This is the site's statement in the site's notation, with the same threshold that the site's commentary gives; the 2026 preprint [ChNi26] restates it as its Theorem 1.2 with the hypotheses and . The theorem's proof is known only through the abstract and that restatement. The accepted claim rests on the refereed note and the curator's credit; the preprint's account below and the third-party Lean proof of the form that this corpus has not built are context, not acceptance evidence. Jiang credits the conjecture to Bollobás's book, where Erdős's papers state it as his own. The theorem is recorded on the claim page Jiang, from which the frontmatter standing is derived; the 2026 preprint has its own claim page, Chen and Ning, as a pending claim, and Pósa's theorem for , credited in the site's commentary, has its own partial claim page, Pósa.