Riscrivo il problema:
Ho un grafo completo con almeno 17 (ok il problema diceva 70? in realtà ne bastano 17
) vertici, i cui lati sono colorati con 3 colori differenti(rosso, giallo e verde).
Devo dimostrare che ho comunque un triangolo monocromatico.
E' noto che $ R(3,3,3) = 17 $ (cui segue la tesi..)
ovvero il minimo n tale che $ G_n $ , grafo completo (con n vertici) i cui lati sono colorati con 3 colori, abbia un sottografo $ G_3 $ completo e monocromatico è 17.
Dimostrazione
Da un vertice A partono almeno 16 lati almeno 6 dei quali dello stesso colore(suppongo sia il rosso).
Considero il vertice A e i 6 vertici di arrivo dei 6 lati rossi.
Se anche solo uno dei lati che connettono due qualsiasi di questi vertici (senza perdita di generalità lo chiamo BC) fosse rosso allora avrei 3 lati rossi: AB,AC,BC e un triangolo monocromatico rosso.
Se nessun lato che connette due qualsiasi di questi vertici è rosso allora ho un grafo completo di 6 vertici da colorare con 2 colori(giallo e verde).
Ma poichè R(3,3)=6 (
per una dimostrazione vedere il problema precedente ) esiste sicuramente un triangolo monocromatico o giallo o verde.
Anche se non richiesto dal problema si può provare che con n=16 esiste almeno una configurazione in cui non ci sia alcun triangolo monocromatico.
Buona serata, Simone.