Erdős problem 1034
Let be a graph on vertices with many edges. Must there be a triangle in and vertices , where , such that every is joined to at least two vertices of ?
Sources
FormalConjectures/ErdosProblems/
1034.lean
Retained formal statement
Let be a graph on vertices with many edges. Must there be a triangle in and vertices , where , such that every is joined to at least two vertices of ?
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 vertices and edges in which every triangle has at most vertices adjacent to at least two of its vertices (note that ).
False ↔ ∀ (ε : ℝ), 0 < ε → ∀ᶠ (n : ℕ) in Filter.atTop, ∀ (G : SimpleGraph (Fin n)), ↑n ^ 2 / 4 < ↑G.edgeSet.ncard → ∃ T, G.IsNClique 3 T ∧ ∃ Y, Erdos1034.JoinedToTwo G T Y ∧ (1 / 2 - ε) * ↑n < ↑Y.card