Teorema di Bondy-Chvátal

Il teorema di Bondy-Chvátal è un teorema della teoria dei grafi relativo ai cicli hamiltoniani. È stato provato nel 1976 dal matematico britannico e canadese John Adrian Bondy e dal matematico polacco Václav Chvátal. Fornisce una condizione necessaria e sufficiente affinché un grafo $G$ sia hamiltoniano. Esso generalizza i teoremi precedenti di Ore e Dirac.

Enunciato

Il teorema afferma che un grafo $G$ è hamiltoniano se e solo se la sua chiusura $[G]$ è hamiltoniana, ossia possiede un ciclo hamiltoniano.

Dimostrazione

Sia $G$ un grafo di $n$ vertici e sia $[G]$ la sua chiusura.
È immediato dimostrare che se un grafo $G$ è hamiltoniano anche la sua chiusura lo è. Infatti $[G]$ è ottenuta da $G$ aggiungendo, se possibile, degli archi, per cui tutti gli archi di $G$ sono anche nella sua chiusura. Di conseguenza se $G$ aveva un ciclo hamiltoniano anche $[G]$ possiede lo stesso ciclo.
Viceversa bisogna ora dimostrare che se $[G]$ è hamiltoniano anche $G$ lo è. Supponiamo che la chiusura di $G$ sia stata creata aggiungendo $K-1$ archi a quelli di $G$. Sia $G_1=G$ e sia $E_1$ l'insieme degli archi di $G$. Sia analogamente $G_K=[G]$ e $E_K$ l'insieme degli archi della chiusura. Necessariamente si ha $E_1\subset E_K$. Per ipotesi $G_K$ è hamiltoniano. Supponiamo per assurdo che $G_1$ non lo sia. Siano $G_2,..G_{j-1},G_j,...,G_K$ i grafi ottenuti per costruire $G_K$ da $G_1$ aggiungendo un arco per volta. Notiamo che se $G_j$ è hamiltoniano allora tutti i grafi $G_i$ con $i\ge j$ sono hamiltoniani in quanto, come prima visto, $E_j\subset E_i$. Se $G_1$ non è hamiltoniano mentre $G_K$ si, allora deve esserci un indice $2\le j\le K$ per il quale $G_j$ è hamiltoniano mentre $G_{j-1}$ non lo è. Poiché a $G_{j-1}$ manca un solo arco affinché venga creato un ciclo hamiltoniano, vuol dire che necessariamente $G_{j-1}$ ha un cammino hamiltoniano $(v_1,v_2,..,v_n)$, dove i vertici sono stati etichettati in modo tale che l'arco che creerebbe il ciclo sia quello che collega i vertici $(v_1,v_n)$. Consideriamo adesso gli insiemi $A=\{v_i|(v_1,v_i)\in E_{j-1}\}$ e $B=\{v_i|(v_n,v_{i-1})\in E_{j-1}\}$ con $2<i<n$. $A$ è l'insieme dei vertici in $G_{j-1}$ che hanno un diretto collegamento con $v_1$, $v_2$ escluso. $B$ è invece l'insieme dei vertici che hanno il vertice che lo precede direttamente collegato con $v_n$. Notiamo che entrambi gli insiemi sono contenuti in $\{v_3,..,v_{n-1}\}$ e vale in particolare che la cardinalità di $A$ è pari $|A|=deg(v_1)-1$ e la cardinalità di $B$ è pari $|B|=deg(v_n)-1$ (gli elementi di $B$ sono in corrispondenza biunivoca con gli archi incidenti su $v_n$ escluso $(v_{n-1},v_n)$ ). Poiché $G_j$ si differenzia da $G_{j-1}$ solo per l'arco tra i vertici $v_1$ e $v_n$, sappiamo, per definizione della costruzione della chiusura di un grafo, che in $G_{j-1}$ vale $deg(v_1)+deg(v_n)\ge n$ e quindi vale anche $|A|+|B|\ge n-2$. Ma sia $A$, sia $B$ sono sottoinsiemi di $\{v_3,..,v_{n-1}\}$ che ha cardinalità $n-3$, ne deduciamo che la loro intersezione è non nulla, ossia che esiste un vertice $v_k$ in comune tra $A$ e $B$. È allora possibile costruire in $G_{j-1}$ il seguente ciclo hamiltoniano $(v_1,...,v_{k-1},v_n,v_{n-1},..v_k,v_1)$, il che è assurdo in quanto è contrario all'ipotesi che $G_{j-1}$ non sia hamiltoniano. Per cui abbiamo dimostrato che se $[G]=G_K$ è hamiltoniano non può esserci un indice $j$ tale che $G_{j-1}$ non sia hamiltoniano e quindi anche $G_1=G$ deve essere hamiltoniano.

Bibliografia

• Template:Cita libro