amici, sconosciuti

[vl4d]

Si consideri il grafo completo con 6 vertici $K_6$, si consideri una colorazione $c$ dei lati del grafo: $c:E(G)->{rosso,blu}$.
Provare che ogni colorazione $c$ da luogo ad un triangolo di vertici di $K_6$ tale che i 3 lati hanno lo stesso colore.

Equivalentemente: se ad una festa si incontrano 6 persone, provare che in ogni caso 3 sono mutuamente amici, oppure 3 sono completi sconosciuti.
(dove la relazione di amicizia e' ovviamente simmetrica)

[elgiovo]

I lati del grafo sono $((6),(2))=15$, i triangoli $((6),(3))=20$. Le colorazioni di un triangolo con due colori sono $2^3=8$, quelle "ammissibili" (che non colorano i lati tutti di rosso o tutti di blu) sono allora 6. I modi di colorare il grafo di rosso e di blu sono $2^15$, mentre i modi possibili di colorare 20 triangoli in modo ammissibile sono $20^6>2^15$, da qui la tesi per pigeonhole.

[vl4d]

aspetta, i 20 triangoli non hanno i lati a due a due disgiunti... perche' dici che puoi colorarli in $20^6$ modi?