Teorema di Bondy-Chvátal

Teorema della teoria dei grafi

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 sia hamiltoniano. Esso generalizza i teoremi precedenti di Ore e Dirac.

EnunciatoModifica

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

DimostrazioneModifica

Sia   un grafo di   vertici e sia   la sua chiusura.
È immediato dimostrare che se un grafo   è hamiltoniano anche la sua chiusura lo è. Infatti   è ottenuta da   aggiungendo, se possibile, degli archi, per cui tutti gli archi di   sono anche nella sua chiusura. Di conseguenza se   aveva un ciclo hamiltoniano anche   possiede lo stesso ciclo.
Viceversa bisogna ora dimostrare che se   è hamiltoniano anche   lo è. Supponiamo che la chiusura di   sia stata creata aggiungendo   archi a quelli di  . Sia   e sia   l'insieme degli archi di  . Sia analogamente   e   l'insieme degli archi della chiusura. Necessariamente si ha  . Per ipotesi   è hamiltoniano. Supponiamo per assurdo che   non lo sia. Siano   i grafi ottenuti per costruire   da   aggiungendo un arco per volta. Notiamo che se   è hamiltoniano allora tutti i grafi   con   sono hamiltoniani in quanto, come prima visto,  . Se   non è hamiltoniano mentre   si, allora deve esserci un indice   per il quale   è hamiltoniano mentre   non lo è. Poiché a   manca un solo arco affinché venga creato un ciclo hamiltoniano, vuol dire che necessariamente   ha un cammino hamiltoniano  , dove i vertici sono stati etichettati in modo tale che l'arco che creerebbe il ciclo sia quello che collega i vertici  . Consideriamo adesso gli insiemi   e   con  .   è l'insieme dei vertici in   che hanno un diretto collegamento con  ,   escluso.   è invece l'insieme dei vertici che hanno il vertice che lo precede direttamente collegato con  . Notiamo che entrambi gli insiemi sono contenuti in   e vale in particolare che la cardinalità di   è pari   e la cardinalità di   è pari   (gli elementi di   sono in corrispondenza biunivoca con gli archi incidenti su   escluso   ). Poiché   si differenzia da   solo per l'arco tra i vertici   e  , sappiamo, per definizione della costruzione della chiusura di un grafo, che in   vale   e quindi vale anche  . Ma sia  , sia   sono sottoinsiemi di   che ha cardinalità  , ne deduciamo che la loro intersezione è non nulla, ossia che esiste un vertice   in comune tra   e  . È allora possibile costruire in   il seguente ciclo hamiltoniano  , il che è assurdo in quanto è contrario all'ipotesi che   non sia hamiltoniano. Per cui abbiamo dimostrato che se   è hamiltoniano non può esserci un indice   tale che   non sia hamiltoniano e quindi anche   deve essere hamiltoniano.

BibliografiaModifica