Erdős problem 617 · problems.science

Let $r\geq 3$ . If the edges of $K_{r^2+1}$ are $r$ -coloured then there exist $r+1$ vertices with at least one colour missing on the edges of the induced $K_{r+1}$ .

Sources

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

4 retained statements2415f78e850a

Open selected source

FormalConjectures/ErdosProblems/

617.lean

Retained formal statement4 of 4

Erdős and Gyárfás [ErGy99] showed this property fails for infinitely many $r$ if we replace $r^2+1$ by $r^2$ .

FormalConjectures/ErdosProblems/617.leanErdos617.erdos_617.variants.r25 linesExact file

1{r |2    ∃ V x x_1,3      Fintype.card V = r ^ 2 ∧4        ∃ coloring,5          ∀ (S : Finset V), S.card = r + 1 → ∀ (k : Fin r), ∃ u ∈ S, ∃ v ∈ S, u ≠ v ∧ coloring s(u, v) = k}.Infinite

SolvedStatement only, no proof

Sources

Search problems.science