---

Claim. The answer to Problem 1034 is no: 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, and $2-\sqrt{5/2}=0.418861\ldots$ is below $\frac12$. The claimed result is Theorem 2.1 of J. Ma and Q. Tang, On Erdős problem #1034, a three-page note hosted on the first author's page (the file the site links; no arXiv identifier or journal; PDF metadata dated 21 October 2025); the corpus states it on the result page Theorem 2.1 (card). The construction is explicit: a side $B$ of $\lfloor\alpha n\rfloor$ vertices partitioned into cliques of about $c_1(\alpha)n$ vertices, an independent side $S$, every edge between $B$ and $S$, and $\alpha^*=1-1/\sqrt{10}$; every triangle has two or three vertices in one clique of $B$, so the vertices joined to two of its vertices are $S$ and that clique, and the edge count exceeds $n^2/4$ by the choice of the clique size. The proof is a two-page computation written out on the problem page. The note reads the site's "every vertex is joined to at least two vertices of $T$" as every $y_i$, the reading the problem page adopts; the count of such vertices is at most $(2-\sqrt{5/2}+\varepsilon)n<(\frac12-o(1))n$ for large $n$, which is the negation of the question under either reading. The thread's first post of 20 October 2025, the page's date, announced the note; an edit to the post corrects its constant: the construction gives $2-\sqrt{5/2}\approx0.4189$, not the smaller constant $\sqrt2-1\approx0.4142$ (a stronger bound) that the earlier version of the note stated, and the authors add that a finer computation might improve the constant slightly; the file the site links is the corrected version. The authors' thread post of 27 October 2025 sketches the further statement that the conjecture fails for $K_4$-free graphs too, with the constant $2\sqrt3-3\approx0.464$; that sketch is not in the note, is unreviewed, and is not part of this claim. The note also records the bounds $(\frac16-o(1))n\le h(n)\le(2-\sqrt{5/2}+o(1))n$ for Erdős's general question, which stays open.

Submission note. Posted to the site's forum by Quanyu Tang on 20 October 2025:

Jie Ma and I have given a negative answer to this problem; see our note (here).

We construct graphs with more than $n^{2}/4$ edges in which every triangle has at most $(2-\sqrt{5/2}+o(1))n$ vertices adjacent to at least two of its vertices.

Hence this disproves the problem. A closer look at the original source of this problem (see also Section 3 of our note) shows that Erdős and Faudree also wrote:

''Perhaps this conjecture is a bit too optimistic, but if it is not true one should try to determine the largest $h(n)$ for which, in every $G(n;\lfloor n^2/4\rfloor+1)$, there is a triangle $(x_1,x_2,x_3)$ and $h(n)$ other vertices which are joined to at least two of the $x$'s.''

Combining our construction with the classical result on the existence of a book of size $n/6$ in every graph with $\lfloor n^2/4\rfloor+1$ edges, we obtain

$$\bigl(\tfrac{1}{6}-o(1)\bigr)n \le h(n) \le (2-\sqrt{5/2}+o(1))n. >$$

EDIT: The note has been updated. We realized that our construction gives

$2-\sqrt{5/2}\approx0.4189$ instead of $\sqrt{2}-1$, though a more careful calculation could show a slightly better constant.

(The site has been updated to address this comment.)

Posted to the site's forum by Quanyu Tang on 27 October 2025:

As the page notes, Erdős also wrote: "Perhaps if our $G$ has no $K_4$, i.e. no vertex is joined to all three of the $x$'s, the answer will be different."

We now point out that even under the $K_4$-free assumption, the statement of this problem is still false. In fact we have the following result:

Theorem. For all sufficiently large $n$ there exists a $K_4$-free graph $G$ on $n$ vertices with

$$e(G)>\frac{n^2}{4} \qquad\text{and}\qquad > \max_{T} |Y(T)| \le (2\sqrt{3}-3+o(1))\,n,$$

where the maximum is over all

triangles $T$ in $G$ and

$$Y(T):=\{\,v\in V(G)\setminus V(T):\, |\{u\in > V(T):\, uv\in E(G)\}|\ge 2\,\}.$$

Proof (sketch). Let $a:=\lfloor

n/\sqrt{3}\rfloor+2$ and $b:=n-a$. Partition $V(G)=A\sqcup B$ with $|A|=a$, $|B|=b$. Make all edges between $A$ and $B$ present, no edges inside $B$, and inside $A$ place a bipartite graph $H$ with a prescribed number $E$ of edges, where

$$E:=\min\{m\in\mathbb{N}:~ab+m>n^2/4\}\qquad(\text{hence }E\le > n^2/4-ab+2).$$

Write $s:=\lfloor a/2\rfloor$ and express $E=rs+t$ with $r\ge

0$ and $0\le t<s$. Split $A=A_1\sqcup A_2$ with $|A_1|=s$, $|A_2|=a-s$, and decompose $K_{A_1,A_2}$ into $s'$ disjoint matchings $M_0,\dots,M_{s'-1}$ (a standard 1-factorization), where $s'\in\{s,s+1\}$. Let $H$ be the union of $r$ full matchings plus $t$ edges of the next one. Then

$$e(H)=E > \quad\text{and}\quad \Delta(H)\le r+1\le \frac{E}{s}+1.$$

By construction

$G[B]$ is independent and $G[A]=H$ is bipartite, so $G$ is $K_4$-free, while $e(G)=ab+e(H)>n^2/4$. Every triangle in $G$ is of the form $\{u,v,w\}$ with $uv\in E(H)$ and $w\in B$. For such $T$,

$$|Y(T)|= > (b-1)+\big(d_H(u)-1\big)+\big(d_H(v)-1\big) = b+d_H(u)+d_H(v)-3 \le > b+2\Delta(H)-3.$$

Hence

$$\max_T |Y(T)| \le b + \frac{2E}{s}+O(1) \le b + > \frac{n^2}{a-2} - \frac{4ab}{a-2}+O(1) = \frac{n^2}{a-2} - 3(n-a) + O(1), >$$

where we used $s\ge (a-2)/2$ and $E\le n^2/4-ab+2$. The right-hand side,

viewed as a function of $c:=a-2$, is minimized at $c=n/\sqrt{3}$ and equals $(2\sqrt{3}-3)n+o(n)$. Since $a=\lfloor n/\sqrt{3}\rfloor+2$, this yields the claimed bound.

(The site has been updated to address this comment.)

Depends on. Nothing in this wiki; the construction and its count are self-contained, and the problem page's deduction of the lower bound on $h(n)$ from Khadzhiivanov's book theorem is not consumed by this claim.

Formalization. The file src/v4.29.1/ErdosProblems/Erdos1034.lean of Boris Alexeev's repository plby/lean-proofs (Lean v4.29.1 with Mathlib v4.29.1, importing Mathlib; 1,575 lines at the pinned commit of 2026-09-15, linked above), announced in the site's forum on 4 December 2025, declares itself a formalization of this solution: its header names Jie Ma, Quanyu Tang and ChatGPT as informal authors and the automated prover Aristotle, Namrata Anand and Alexeev as formal authors. It defines the graph MaTangGraph n α s of the note with alpha_star = 1 - 1/√10, proves MaTang_main, that for every $\varepsilon>0$ and all large $n$ the graph has more than $n^2/4$ edges and every triangle has at most $(2-\sqrt{5/2}+\varepsilon)n$ vertices with two neighbors in it, and then proves not_erdos_1034, the negation of its own erdos_1034: for every $\varepsilon>0$ and all large $n$, every graph on $n$ vertices with more than $n^2/4$ edges has a triangle with more than $(\frac12-\varepsilon)n$ vertices joined to two of its vertices. That erdos_1034 is the collection's statement of the problem with its $Y$ taken as the full set of vertices with two neighbors in $T$, an equivalent form (the problem page transcribes both). Comments after #print axioms MaTang_main and #print axioms not_erdos_1034 report the axioms propext, Classical.choice and Quot.sound, and the file contains no sorry, axiom, native_decide or unsafe. The repository's note ErdosProblems/Erdos1034.md (the record link) lists copies for five toolchains (Lean v4.24.0 to v4.33.0). Nothing was built, replayed or audited here, and the fidelity of its statement to the question was not independently reviewed by this project, so the page lists no formalized evidence.

Acceptance. The reviewed evidence is the site's documented acceptance: the site's curator, Thomas Bloom, labels the problem DISPROVED (LEAN) and credits Ma and Tang with the disproof in the commentary, which describes the construction and the constant (page last edited 28 October 2025, after the thread posts of 20 and 27 October 2025, both marked by the site as addressed; Bloom took no part in the note); Bloom's thread comment of 13 August 2026 treats the Erdős--Faudree guess as refuted with the true order of $h(n)$ open; the proof-claim tab is empty; the community database lists "disproved (Lean)" as of its last update of 4 December 2025, without a date for the change of state. The problem's standing rests on this acceptance. No refereed publication, arXiv version or written independent review of the note was found on 2026-09-19 (the search scope is on the problem page), so no refereed evidence is listed. Read depth here: Conjecture 1.1 and Theorem 2.1 checked clause by clause; the proof followed, not checked step by step; nothing is independently reviewed by this project.