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>(12−o(1))nt>(\frac{1}{2}-o(1))n, such that every yiy_i is joined to at least two vertices of TT?

Erdős Problems records this as disproved (Lean).

No Repository has ruled on it here.

How far the record reaches4 of 6 stages
  1. Sourceerdos-problems
  2. StatementRetained
  3. Formal4 retained
  4. Resolutiondisproved (Lean)
  5. WorkNone recorded
  6. DecisionNone here
  7. The questionNot reached
What this record is missingWork

Nothing here has checked that finding.

Reproducing it here turns a report into evidence.

Where the source files it274 share a topic
None carries a Standing. Browse the topic.