Don't take life too seriously: it's just a temporary situation

Tait (congettura di)

Congetture  Teoria dei grafi 

Nel 1884 P.G. Tait avanzò la congettura che ogni grafo planare (ossia disegnabile sul piano senza incroci), trivalente (ossia tale che ogni nodo sia l’estremo di esattamente 3 archi) e 3-connesso (ossia che non si divida in parti separate rimuovendo due nodi qualsiasi) abbia un circuito hamiltoniano, ossia un percorso chiuso che passa esattamente una volta da ogni nodo.

 

La congettura, che Tait dava per scontata, era una parte fondamentale della sua dimostrazione del teorema dei quattro colori (v. numeri di Heawood), perché Tait aveva stabilito una corrispondenza tra le mappe e i grafi planari trivalenti e 3-connessi. Il matematico aveva mostrato che una mappa è colorabile con 4 colori se e solo se gli archi del grafo corrispondente possono essere colorati con 3 colori, in modo che in ogni nodo concorra un arco di ciascun colore.

 

Nel 1976 Martin Gardner in un articolo chiamò “snark” i grafi trivalenti, 3-connessi non colorabili con 3 colori in modo che ogni vertice sia comune a tre archi di colori diversi; il termine è molto più corto della frase che descrive questi grafi, piacque e da allora è comunemente utilizzato. Gardner si rifaceva al poema “The Hunting of the Snark” (“La caccia dello snark”) di Lewis Carrol, nel quale lo snark è una creatura fantastica, molto elusiva.

La congettura di Tait si può quindi esprimere dicendo che afferma che gli snark non sono planari.

 

Nel 1946 William Thomas Tutte (Newmarket, UK, 14/5/1917 – Kitchener, Canada, 2/5/2002) pubblicò un controesempio alla congettura di Tait, ossia un grafo planare trivalente privo di circuito hamiltoniano, mostrato nella figura seguente.

 

Controesempio di Tutte alla congettura di Tait

 

La dimostrazione sul fatto che il grafo non ammette un circuito hamiltoniano si basa sul “frammento di Tutte”, mostrato nella figura seguente.

 

Frammento di Tutte

 

Un cammino hamiltoniano in questa parte del grafo deve entrare dal nodo superiore e uscire da uno dei due nodi laterali inferiori o viceversa; non può entrare da uno dei due nodi laterali inferiori e uscire dall’altro. Combinando tre di questi frammenti si ottiene il grafo di Tutte e considerando i modi di entrare e uscire dai frammenti si dimostra che un percorso hamiltoniano chiuso è impossibile.

Il grafo di Tutte è colorabile con 3 colori e non costituisce un controesempio al teorema dei 4 colori: l’esistenza di un circuito hamiltoniano si era rivelata condizione sufficiente, ma non necessaria perché un grafo fosse colorabile con 3 colori.

Il grafo è planare e trivalente, quindi il teorema dimostrato da Ernst Steinitz (Laurahütte, Germania, 13/6/1871 – Kiel, Germania, 29/9/1928) nel 1922 assicura che corrisponde agli spigoli di un poliedro convesso. Successivi raffinamenti permisero di dimostrare che ogni grafo planare trivalente corrisponde agli spigoli di un poliedro convesso con tutte le cordinate dei vertici intere e a uno nel quale tutti gli spigoli sono tangenti a una stessa sfera.

Il controesempio di Tutte mostra che non tutti i poliedri semplici (ossia tale che ogni vertice sia comune a esattamente 3 facce) ammettono un circuito hamiltoniano lungo gli spigoli.

 

Nel 1988 D.A. Holton e Brendan D. McKay dimostrarono che non esistono controesempi alla congettura 3-connessi con meno di 38 nodi e che ne esistono esattamente 6 con 38 nodi, costruiti nel 1965 da Barnette, Bosák e Lederberg rimpiazzando due nodi del grafo corrispondente a un prisma pentagonale con due frammenti di Tutte.

La figura seguente mostra uno dei 6 grafi.

 

Controesempio di Holton e McKay alla congettura di Tait

 

 

Nel 1971 Tutte cercò di modificare la congettura, sostituendo la condizione che il grafo sia planare con quella che sia bipartito (ossia tale che i nodi siano suddivisi in due insiemi e ciascuno sia connesso solo ai nodi dell’altro insieme), ma senza successo (v. congettura di Tutte).

La congettura di Barnette, che unisce le condizioni delle congetture di Tait e Tutte sembra invece valida.

Contattami

Potete contattarmi al seguente indirizzo bitman[at]bitman.name per suggerimenti o segnalazioni d'errori relativi a questo articolo.