Problem 905

Every graph with $n$ vertices and $>n^2/4$ edges contains an edge which is in at least $n/6$ triangles.

Graph theory

Wiki page

Status

SolvedProved

An accepted solution exists. The statement is true.

Proved. The status-defining source the site names, N. G. Khadzhiivanov and V. Nikiforov, Solution of a problem of P. Erdős about the maximum number of triangles with a common edge in a graph, C. R. Acad. Bulgare Sci. 32 (1979), no. 10, 1315--1318 [KhNi79] (the site's reference text prints the second author as "S. V. Nikiforov"; the 1988 paper, Fox and Loh and Bollobás and Nikiforov give V. Nikiforov), is not held and has no online record located, and the site marks its second prover, Edwards, as unpublished. The label rests on five sources. First, the refereed paper of Bollobás and Nikiforov, Books in graphs, European J. Combin. 26 (2005) [BoNi05], cited from its arXiv version: its Corollary 3 states that every $G(n,\lfloor n^2/4\rfloor+1)$ has a book of size greater than $n/6$ , and the proof of its Corollary 2 derives $6\,\mathrm{bk}(G)>n$ for every $m>n^2/4$ from a counting inequality (its Theorem 1) that uses arguments of the 1979 note; a complete proof of the statement in a refereed journal, whose introduction credits the first proofs to Edwards's unpublished manuscript and, independently, to [KhNi79]. Second, the 1988 paper of Khadzhiivanov (Khadzhiivanov 1988, Annuaire Univ. Sofia 82 (1988), 37--49, in Russian; a university journal), which states the problem in the site's exact form, attributes its complete solution to the 1979 note with Nikiforov, and proves it again with a surplus as its Corollary 3 (Khadzhiivanov 1988): if $e>\lfloor n^2/4\rfloor$ then $\hat t>n/6$ , from the inequality $(3t+\bar t)\hat t\ge nt$ (its Theorem 1, which the paper says, in translation, the 1979 note proves a little differently) and the bound $\sum_vd(v)^2>ne$ (its Lemma 4); its statements are checked clause by clause and its proofs only for structure. Third, a refereed attestation: Fox and Loh (Combinatorica 32 (2012); p. 2 of the preprint, recorded on the card for Problem 80) state that Edwards and Khadzhiivanov and Nikiforov proved that every $n$ -vertex graph with more than $n^2/4$ edges has an edge in at least $n/6$ triangles. Fourth, the site's account and the community database. Fifth, the external Lean file named by the formal-conjectures statement, which has no recorded build (Formalization). The 1979 text itself is not held, so the exact statement it proves and its proof are known through the 1988 paper's own account and [BoNi05]'s attribution. Erdős's own 1982 report of the problem's history ([Er82e], p. 71) is quoted below with a contradiction it carries into Problem 1033. The claim pages are Khadzhiivanov and Nikiforov (accepted on the 1988 reproof, Fox and Loh's attestation and the site's credit; the frontmatter standing is derived from the accepted pages), Bollobás and Nikiforov (accepted on the refereed publication; its second author shares the 1979 coauthor's name, so it is not counted as independent acceptance of the 1979 note) and Edwards (accepted on the site's curator's credit; the proof was never published, and Khadzhiivanov's 1988 paper reads the 1978 announcement as not solving the conjecture); the external Lean proof behind the site's suffix declares itself a formalization of the 1979 note's result and is recorded as a formalization link on the first page, with no build of it recorded.

KhNi79: Khadzhiivanov, N. G. and Nikiforov, V., Solution of a problem of P. Erdős about the maximum number of triangles with a common edge in a graph. C. R. Acad. Bulgare Sci. 32 (1979), no. 10, 1315--1318 (in Russian per its 1988 citation, "Dokl. BAN 32, No. 10, 1979"). The coauthor is V. (Vladimir) Nikiforov: [Kh88]'s reference [2] prints "Вл. Никифоров" and its p. 44 calls him, in translation, the author's diploma student V. Nikiforov, and [FoLo12]'s reference [13] and [BoNi05]'s reference [10] give "V. Nikiforov"; the site's reference text prints "S. V. Nikiforov". Not held; no DOI; its theorem is known through [Kh88], [BoNi05] and [FoLo12].
Kh88: Khadzhiivanov, N., On the maximal number of triangles with a common edge (in Russian, with an English abstract and summary). Annuaire Univ. Sofia "St. Kliment Ohridski", Fac. Math. Inform., Livre 1, 82 (1988), 37--49 (the journal's article record dates the volume 12 December 1991; zbMATH lists pp. 37--52). Not a site key. Erdős's problem with its history, p. 44; Theorem 1 and the extremal examples, p. 40; Corollaries 1--2, p. 41; Lemma 4, pp. 44--45; Corollaries 3--5, p. 45; the account of Edwards's announcement, pp. 47--48. Library home: Khadzhiivanov 1988; paged at Khadzhiivanov 1988, Erdős's problem (p. 44 = PDF p. 8) and Khadzhiivanov 1988, Corollary 3 (p. 45 = PDF p. 9).
BoNi05: Bollobás, Béla and Nikiforov, Vladimir, Books in graphs. European J. Combin. 26 (2005), no. 2, 259--270, doi:10.1016/j.ejc.2004.01.007 (Crossref record: issue dated February 2005, record created 17 April 2004; Elsevier open archive). Preprint arXiv:math/0405080, v1 of 5 May 2004 (13 pages, with the comment "accepted in Eur. J. Combin"), the version cited: Section 2, the introduction's attribution of the first proofs, Theorem 1, Corollary 2 (attributed to Edwards, its reference [3]) and Corollary 3; references [3] and [10]. Not a site key; [FoLo12]'s reference [2] and the Lean file's [BoNi04]. Not held as a filed source.
Ed78b: Edwards, C. S., The largest number of triangles with a common edge in a graph. Colloques internationaux C.N.R.S. 260 (Problèmes combinatoires et théorie des graphes, Orsay 1976), Paris (1978), 123--126, as [Kh88]'s reference [3] gives it; the site's "Edwards (unpublished)". Not held; [Kh88] (p. 48) says, in translation, that its theorems were announced with the intention of publishing their proofs later, which had not happened in the ten years since. The manuscript itself is [BoNi05]'s reference [3], C. S. Edwards, A lower bound for the largest number of triangles with a common edge, unpublished manuscript, 1977 (also [FoLo12]'s reference [4]). Not held.
Er75: Erdős, P., Some recent progress on extremal problems in graph theory. Congr. Numer. XIV (1975), 3--14; Chapter 4, printed p. 13. Library home: Erdős 1975; the passage is paged at Erdős 1975, Problem (Chapter 4, printed p. 13 = PDF p. 11).
Er82e: Erdős, Paul, Some of my favourite problems which recently have been solved. Proceedings of the International Mathematical Conference (Singapore, 1981), North-Holland Math. Stud. 74 (1982), 59--79; §5, printed p. 71. Library home: Erdős 1982.
Er93: Erdős, Paul, Some of my favorite solved and unsolved problems in graph theory. Quaestiones Math. 16 (1993), 333--350. Chapter V, problem 4, printed p. 344: the Bollobás--Erdős book conjecture, its sharpness, and "Edwards [47] proved our conjecture, but his proof unfortunately has never been published", its reference [47] (p. 349) describing that proof as an unpublished manuscript available from a colleague at Memphis State University; the survey does not name Khadzhiivanov and Nikiforov. Library home: Erdős 1993.
FoLo12: Fox, J. and Loh, P.-S., On a problem of Erdős and Rothschild on edges in triangles. Combinatorica 32 (2012), no. 6, 619--628; p. 2 of the preprint, the attestation. Not a site key for this problem. Library home: Fox and Loh 2012.
BoEr75: Bollobás, B. and Erdős, P., Unsolved problems. Proc. Fifth British Combinatorial Conference (Aberdeen, 1975), Congr. Numer. XV (1976), 678--680, as [Kh88]'s reference [6] and Bollobás--Nikiforov 2005 give it; [Kh88] says, in translation, that the conjecture takes there the more precise form $\hat t\ge n/6$ . Not a site key for this problem; not held.

Problem 905

Status

Proof claims

Discussion