Problem 1009

Is it true that, for every $c>0$ , there exists $f(c)$ such that every graph on $n$ vertices with at least $\lfloor n^2/4\rfloor+k$ edges, where $k<c n$ , contains at least $k-f(c)$ many edge disjoint triangles?

Source: erdosproblems.com/1009

Graph theory

Wiki page

Status

SolvedProved

An accepted solution exists. The statement is true.

Proved. The site credits Győri [Gy88] with the proof and adds, as its reading of the paper, that $f(c)\ll c^2$ and that no loss occurs ( $f(c)=0$ ) when $n$ is odd and $c<2$ , or when $n$ is even and $c<3/2$ ; the no-loss sentence is a statement for $n$ large in terms of $c$ (the Current assessment records the small cases that refute it as an all- $n$ statement). Győri's paper (Combinatorics (Eger, 1987), Colloq. Math. Soc. János Bolyai 52, North-Holland (1988), 267--276) is print-only and not held. Its theorem is attested in a refereed later paper, Blumenthal, Lidický, Pehova, Pfender, Pikhurko and Volec (Combin. Probab. Comput. 30 (2021), 271--287), whose p. 8 (arXiv version) quotes "the result of Győri [12, Theorem 1] that a graph with $n$ vertices and $t_2(n)+k$ edges, where $n\to\infty$ and $k=o(n^2)$ , has at least $k-O(k^2/n^2)$ edge-disjoint triangles" and whose Section 5 states the exact no-loss ranges for large $n$ , and, for the same ranges, in the refereed paper of Balogh and Wigal (arXiv:2502.16683v2, p. 10). With $k<cn$ the loss $O(k^2/n^2)$ is $O(c^2)$ for all large $n$ , which is the site's $f(c)\ll c^2$ (an authored conversion below). The label rests on Erdős's question, the site's acceptance and the refereed quotation; the text of the theorem, its constants and its range of $n$ are not available, which the Remaining gaps below record. The claim page Győri 1988 records the result, its attestations, the acceptance evidence and the Lean development of 2026 that declares itself a formalization of the result; the standing in the frontmatter is derived from it.

Gy88: Győri, E., On the number of edge-disjoint triangles in graphs of given size. Combinatorics (Eger, 1987), Colloq. Math. Soc. János Bolyai 52, North-Holland, Amsterdam (1988), 267--276; Zbl 0706.05029 (the zbMATH record identifies the volume and carries a review). Not held: a print-only proceedings volume with no online route. Quoted second-hand from [BLPPPV21] and [BaWi25].
Er71: Erdős, P., Some unsolved problems in graph theory and combinatorial analysis. Combinatorial Mathematics and its Applications (Proc. Conf., Oxford, 1969), Academic Press (1971), 97--109; item 3, p. 98. Library home: Erdős 1971; the passage is paged at Erdős 1971, Item 3 (p. 98).
Er62d: Erdős, P., On a theorem of Rademacher--Turán. Illinois J. Math. 6 (1962), 122--127; Erdős's reference [5] in item 3, the source of the Erdős--Gallai theorem his proof uses. Library home: Erdős 1962 (not consumed on this page).
BLPPPV21: Blumenthal, A., Lidický, B., Pehova, Y., Pfender, F., Pikhurko, O. and Volec, J., Sharp bounds for decomposing graphs into edges and triangles. Combin. Probab. Comput. 30 (2021), no. 2, 271--287, doi:10.1017/S0963548320000358; arXiv:1909.11371v3 (11 June 2020), the open copy used (its p. 8, the proof of Lemma 11, and its Section 5, the related results); the library's card is Blumenthal 2021.
BaWi25: Balogh, J. and Wigal, M. C., Packing edge disjoint cliques in graphs. arXiv:2502.16683v2 (14 September 2025, "Updated with referees' suggestions"); published in Combinatorica 45 (2025), no. 5, article 56, doi:10.1007/s00493-025-00184-w (Crossref record; the journal text is not compared). Its p. 10 is the passage used; the library's card is Balogh and Wigal 2025. Its reference [9], Győri, Edge disjoint cliques in graphs, Sets, graphs and numbers (Budapest, 1991), Colloq. Math. Soc. János Bolyai 60 (1992), 357--363, is cited there "for minor correction" of [Gy88]; not held.
GyKe17: Győri, E. and Keszegh, B., On the number of edge-disjoint triangles in $K_4$ -free graphs. Combinatorica 37 (2017), 1113--1124. Library home: Győri and Keszegh 2017 (the arXiv version); the $K_4$ -free case with no loss, the site's Problem 1017; its introduction does not quote [Gy88]'s general theorem, so it is context on this page, not an attestation.

Problem 1009

Status

Proof claims

Discussion