Coloriamo un grafo
Coloriamo un grafo
Tutti gli archi di un grafo completo di 9 vertici sono colorati o di rosso o di blu. Dimostrare che ci sono 4 vertici con tutti gli archi che li congiungono blu oppure 3 vertici con tutti gli archi che li congiungono rossi.
Re: Coloriamo un grafo
Per $ n- $grafo si intenda un grafo completo di $ n $ vertici
La tesi del problema è che o esiste un 4-grafo blu (1) o esiste un 3-grafo rosso (2)
Ragioniamo per assurdo: esiste una colorazione che non prevede nè (1) nè (2).
Supponiamo di determinare questa colorazione: iniziamo creando 3 diversi 3-grafi blu sui 9 vertici del grafo in modo che i 3-grafi non abbiano vertici in comune; a questo punto continuo a colorare archi di blu avendo accortezza di non creare 4-grafi. In particolare, chiamando con $ A_n , B_n , C_n $ i vertici dell' n-esimo 3-grafo blu:
- I vertici $ A_1,A_2,A_3 $ si possono unire a formare un 3-grafo, come anche i vertici $ B_n $ e $ C_n $
- I vertici $ A \; e \; B $ si uniscono in modo ciclico, ovvero colorando gli archi $ A_1 B_2 \; , \; A_2 B_3 \; , \; A_3 B_1 $, come anche i vertici $ B \; e \; C $ e i vertici $ C \; e\; A $
A questo punto non posso colorare ulteriormente archi di blu altrimenti creerei un 4-grafo: infatti il vertice $ A_n $ è collegato mediante un arco blu con i vertici $ A_{n-1}\;,\;A_{n+1}\;,\;C_{n-1}\;,\;B_{n+1} $. Se dovessi collegare in blu i vertici $ C_{n-1}\;e\;A_{n+1} \;,\;A_{n-1}\;e\;B_{n+1}\;o\;C_{n-1}\;e\;B_{n+1} $ si creerebbe un 4-grafo blu, quindi questi archi sono necessariamente rossi.
Ma questo porta all'assurdo, poichè si creano in questo modo i 3-grafi rossi $ A_n\;,\;B_{n-1}\;,\;C_{n+1} $, quindi non esiste una tale colorazione e la tesi è dimostrata.
La tesi del problema è che o esiste un 4-grafo blu (1) o esiste un 3-grafo rosso (2)
Ragioniamo per assurdo: esiste una colorazione che non prevede nè (1) nè (2).
Supponiamo di determinare questa colorazione: iniziamo creando 3 diversi 3-grafi blu sui 9 vertici del grafo in modo che i 3-grafi non abbiano vertici in comune; a questo punto continuo a colorare archi di blu avendo accortezza di non creare 4-grafi. In particolare, chiamando con $ A_n , B_n , C_n $ i vertici dell' n-esimo 3-grafo blu:
- I vertici $ A_1,A_2,A_3 $ si possono unire a formare un 3-grafo, come anche i vertici $ B_n $ e $ C_n $
- I vertici $ A \; e \; B $ si uniscono in modo ciclico, ovvero colorando gli archi $ A_1 B_2 \; , \; A_2 B_3 \; , \; A_3 B_1 $, come anche i vertici $ B \; e \; C $ e i vertici $ C \; e\; A $
A questo punto non posso colorare ulteriormente archi di blu altrimenti creerei un 4-grafo: infatti il vertice $ A_n $ è collegato mediante un arco blu con i vertici $ A_{n-1}\;,\;A_{n+1}\;,\;C_{n-1}\;,\;B_{n+1} $. Se dovessi collegare in blu i vertici $ C_{n-1}\;e\;A_{n+1} \;,\;A_{n-1}\;e\;B_{n+1}\;o\;C_{n-1}\;e\;B_{n+1} $ si creerebbe un 4-grafo blu, quindi questi archi sono necessariamente rossi.
Ma questo porta all'assurdo, poichè si creano in questo modo i 3-grafi rossi $ A_n\;,\;B_{n-1}\;,\;C_{n+1} $, quindi non esiste una tale colorazione e la tesi è dimostrata.