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 statement2 of 4

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

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