Skip to content

Erdős problem 617

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

Sources

The source's own material, retained exactly.

4 retained statements36c6d0fef71a

Open selected source

FormalConjectures/ErdosProblems/

617.lean

Retained formal statement3 of 4

Erdős and Gyárfás [ErGy99] proved the conjecture for r=4r=4.

FormalConjectures/ErdosProblems/617.leanErdos617.erdos_617.variants.r_eq_44 linesExact file
∀ r ≥ 3,  ∀ {V : Type} [inst : Fintype V] [DecidableEq V],    Fintype.card V = 4 ^ 2 + 1 →      ∀ (coloring : Sym2 V → Fin 4), ∃ S k, S.card = 4 + 1 ∧ ∀ u ∈ S, ∀ v ∈ S, u ≠ v → coloring s(u, v) ≠ k
SolvedStatement only, no proof