Grafo completo con 7 vertici
Inviato: 12 lug 2013, 21:47
Sia dato un grafo completo con 7 vertici tale che ogni arco é colorato di blu o di rosso.Mostrare che ci sono almeno 4 triangoli monocromatici all' interno del grafo.
Testo nascosto:
Siano $v_i$ i vertici con i=1,..,7. Definisco angolo monocromatico l'angolo $\angle{v_iv_jv_k}$ se $v_iv_j$ e $v_jv_k$ hanno lo stesso colore. È facile dimostrare che per ogni vertice ci sono almeno 6 angoli monocromatici per un totale di almeno 42 angoli monocromatici. Sia k il numero di trangoli monocromatici, si ha che ogni triangolo monocromatico ha 3 angoli monocromatici mentre gli altri ne hanno uno solo e dato che i triangoli totali sono 35, il numero degli angoli cromatici è pari a 3k+(35-k)=35+2k. Ora, poiché gli angoli cromatici sono almeno 42 si ha che $35+2k\geq 42$, il che comporta $k\geq4$ che è la tesi.