Skip to content

Erdős problem 1034

Let GG be a graph on nn vertices with >n2/4>n^2/4 many edges. Must there be a triangle TT in GG and vertices y1,,yty_1,\ldots,y_t, where t>(12o(1))nt>(\frac{1}{2}-o(1))n, such that every yiy_i is joined to at least two vertices of TT?

Sources

Browse retained paths and inspect the exact material available for this Problem.

4 retained statements2415f78e850a

Open selected source

FormalConjectures/ErdosProblems/

1034.lean

Retained formal statement1 of 4

Let GG be a graph on nn vertices with >n2/4>n^2/4 many edges. Must there be a triangle TT in GG and vertices y1,,yty_1,\ldots,y_t, where t>(12o(1))nt>(\frac{1}{2}-o(1))n, such that every yiy_i is joined to at least two vertices of TT?

A conjecture of Erdős and Faudree; a stronger version of [905].

This has been solved in the negative by Ma and Tang [MaTa25], who construct a graph with nn vertices and >n2/4>n^2/4 edges in which every triangle has at most (2(5/2)1/2+o(1))n(2-(5/2)^{1/2}+o(1))n vertices adjacent to at least two of its vertices (note that 2(5/2)1/20.41892-(5/2)^{1/2}\approx 0.4189).

FormalConjectures/ErdosProblems/1034.leanErdos1034.erdos_10347 linesExact file
False  ∀ (ε : ℝ),    0 < ε →      ∀ᶠ (n : ℕ) in Filter.atTop,        ∀ (G : SimpleGraph (Fin n)),n ^ 2 / 4 < ↑G.edgeSet.ncardT, G.IsNClique 3 T ∧ ∃ Y, Erdos1034.JoinedToTwo G T Y ∧ (1 / 2 - ε) * ↑n < ↑Y.card
SolvedProof has a holelean4external proof

The proof uses `sorry`: part of the argument is written but not proved. Lean accepts the file; it does not accept the theorem.

Search problems.science

Find a Problem, Result, source, or page