Kuratowski ed il teorema dei 4 colori

Domande di teoria, mini-dispense degli utenti, richieste di riferimenti ad articoli, ...

Moderatore: Moderatori

Messaggioda Endomorfismo il gio 8 mar 2012, 15:57

hydro ha scritto:
Endomorfismo ha scritto:Scusa, riformulo.
Supponiamo che il teorema dei quattro colori sia falso. Allora esiste un grafo planare che non è 4-colorabile. Quindi, in questo grafo, ci sarebbe un punto A connesso sia con due punti B e C tra loro connessi, sia con almeno tre punti connessi con B e C, oppure con almeno due punti D ed E connessi con B e C e tra di loro.


Questo passaggio non è per nulla chiaro (almeno per me). Come fai a dimostrare che dal fatto che non esista nessuna 4-colorazione segue necessariamente una di queste 2 situazioni?

Iniziamo a colorare il grafo, nella zona incriminata. Abbiamo un primo punto A, che coloriamo col colore che vogliamo. A è collegato a B, che dev'essere pertanto colorato con un secondo colore. B è collegato a C, ma a meno che C non sia collegato anche con A possiamo colorarlo col primo colore. Visto che per ipotesi non ce ne devono bastare quattro di colori, C deve essere collegato sia ad A che a B. Lo dobbiamo quindi colorare con un terzo colore. Per essere costretti ad usare il quarto colore, dovremmo avere un punto D collegato con punti colorati con gli altri tre colori, altrimenti potremmo anche colorarlo col colore mancabile. Quindi D è connesso ad A, B e C. Per essere obbligati ad usare un quinto colore, dovremmo avere un punto E collegato a tutti e quattro i punti precedenti (avremmo quindi disegnato un K_5), oppure due punti E ed F collegati ad A, B e C allo stesso modo di D (e ci troveremmo di fronte a un K_{3,3}). In caso contrario, c'è sempre un modo per riutilazzare un colore.
Endomorfismo
 
Messaggi: 19
Iscritto il: sab 3 mar 2012, 16:26
Località: Una causalmente connessa con la tua

Precedente

Torna a Teoria

Chi c’è in linea

Visitano il forum: Nessuno e 1 ospite

cron