Problem 1034

Let $G$ be a graph on $n$ vertices with $>n^2/4$ many edges. Must there be a triangle $T$ in $G$ and vertices $y_1,\ldots,y_t$ , where $t>(\frac{1}{2}-o(1))n$ , such that every vertex is joined to at least two vertices of $T$ ?

Source: erdosproblems.com/1034

Graph theory

Wiki page

Status

SolvedDisproved

An accepted solution exists. The statement is false.

Disproved. The status-defining source is Theorem 2.1 of a three-page note by Jie Ma and Quanyu Tang, On Erdős problem #1034 (the file the site links on the first author's page; no arXiv identifier or journal; PDF metadata 21 October 2025): for every $\varepsilon>0$ and all sufficiently large $n$ there is a graph on $n$ vertices with more than $n^2/4$ edges in which no triangle has more than $(2-\sqrt{5/2}+\varepsilon)n$ vertices with two or more neighbors on it, where $2-\sqrt{5/2}=0.418861\ldots<\frac12$ . The construction is explicit (a complete bipartite graph between a side $B$ of $\lfloor\alpha n\rfloor$ vertices partitioned into cliques of about $c_1(\alpha)n$ vertices and an independent side, optimized at $\alpha^*=1-1/\sqrt{10}$ ) and the proof is a two-page computation, followed here. The claim page Ma and Tang records the disproof as accepted on the site's documented acceptance (its label DISPROVED (LEAN), the page last edited 28 October 2025; the community database lists "disproved (Lean)" as of its last update of 4 December 2025) and carries, as a formalization link, the external Lean file that declares itself a formalization of the note's solution and proves the negation of the formalized statement, not built here. This is a source-supported solution accepted by the site, distinct from a claim of journal refereeing; the site's Lean suffix is its catalog label for that external proof, which this corpus has not built or audited. Erdős's general question, the largest $h(n)$ for which every such graph has a triangle and $h(n)$ other vertices joined to two of its vertices, stays open between $(\frac16-o(1))n$ and $(2-\sqrt{5/2}+o(1))n$ .

MaTa25: Ma, J. and Tang, Q., On Erdős problem #1034. Three-page note, http://staff.ustc.edu.cn/~jiema/Erdos-1034.pdf (the site's link); no arXiv identifier or journal; PDF metadata dated 21 October 2025; its reference [1] cites the site "accessed 2025-10-20"; the version with the constant $2-\sqrt{5/2}$ (the thread's 20 October 2025 post says an earlier version gave $\sqrt2-1$ ). Conjecture 1.1 and Theorem 2.1, p. 1; the proof, pp. 1--2; Section 3 with the quotation of [Er93], p. 3. Library home: Ma and Tang 2025; paged at Ma and Tang 2025, Theorem 2.1 (p. 1) and Ma and Tang 2025, Section 3 (p. 3).
Er93: Erdős, P., Some of my favorite solved and unsolved problems in graph theory. Quaestiones Math. 16 (1993), 333--350; p. 344 per the site's key and the note. Chapter V, problem 4, printed p. 344: the Erdős--Faudree "stronger conjecture", the words "Perhaps this conjecture is a bit too optimistic", the general question for $h(n)$ and the $K_4$ -free remark, stated without proof after the Bollobás--Erdős book conjecture of Problem 905. Library home: Erdős 1993.
Kh88: Khadzhiivanov, N., On the maximal number of triangles with a common edge (in Russian). Annuaire Univ. Sofia, Fac. Math. Inform. 82 (1988), 37--49; Corollary 3, p. 45, and Theorem 2, p. 43, in the card's translation. Library home: Khadzhiivanov 1988; paged at Khadzhiivanov 1988, Corollary 3 (p. 45 = PDF p. 9). Not a site key; the book theorem of Problem 905 behind the lower bound on $h(n)$ (the original 1979 note of Khadzhiivanov and Nikiforov, the site's KhNi79 on Problem 905, is not held).
Er82e: Erdős, P., 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. Not a site key for this problem; the Bollobás--Erdős book conjecture with its "best possible" remark, the statement this problem strengthens. Library home: Erdős 1982.

Problem 1034

Status

Proof claims

Discussion