Teorema di Ore

Il teorema di Ore è un teorema della teoria dei grafi provato nel 1960 dal matematico Norvegese Øystein Ore. Fornisce una condizione sufficiente, ma non necessaria, affinché un grafo sia Hamiltoniano, affermando che un grafo che contiene un sufficiente numero di archi, comparati al numero di vertici, deve contenere un ciclo Hamiltoniano. Esso è inoltre una generalizzazione del teorema di Dirac e a sua volta viene generalizzato dal teorema di Bondy-Chvátal.

Enunciato

Sia ${\displaystyle G}$ un grafo semplice con un numero finito di vertici ${\displaystyle n\geq 3}$. Sia ${\displaystyle deg(v)}$ il grado del vertice ${\displaystyle v}$, ossia il numero di archi incidenti su ${\displaystyle v}$. Allora il teorema di Ore stabilisce che, presi due vertici ${\displaystyle v}$ e ${\displaystyle w}$ non adiacenti, se vale ${\displaystyle deg(v)+deg(w)\geq n}$ allora ${\displaystyle G}$ è Hamiltoniano.

Dimostrazione

Usando il teorema di Bondy-Chvátal, la dimostrazione è immediata.

Una possibile dimostrazione diretta è invece la seguente:

Basterà dimostrare che se il grafo non è Hamiltoniano allora la condizione data dal teorema di Ore viene violata. Sia quindi ${\displaystyle G}$ un grafo privo di cicli hamiltoniani e sia ${\displaystyle H}$ il grafo ottenuto da ${\displaystyle G}$ aggiungendo archi fin quando l'aggiunta di un altro arco produrrebbe un ciclo hamiltoniano. Poiché l'aggiunta di un solo arco creerebbe un ciclo hamiltoniano allora necessariamente ${\displaystyle H}$ possiede un cammino hamiltoniano ${\displaystyle (v_{1},v_{2},...,v_{n-1},v_{n})}$, dove gli ${\displaystyle n-}$vertici sono stati ordinati in modo tale che l'arco la cui aggiunta creerebbe il ciclo sia ${\displaystyle (v_{1},v_{n})}$, che risultano essere quindi due vertici non adiacenti sia in ${\displaystyle H}$ che in ${\displaystyle G}$ . Per ogni ${\displaystyle 2\leq i\leq n}$ consideriamo l'arco ${\displaystyle (v_{1},v_{i})}$. Se questo arco esiste, ossia se ${\displaystyle v_{i}}$ fa parte dell'insieme dei vicini di ${\displaystyle v_{1}}$, allora necessariamente non deve esistere l'arco ${\displaystyle (v_{i-1},v_{n})}$ poiché tale arco produrrebbe un ciclo hamiltoniano in ${\displaystyle H}$ che per ipotesi ne è privo. Infatti un possibile ciclo sarebbe ${\displaystyle (v_{1},..,v_{i-1},v_{n},v_{n-1},...,v_{i},v_{1})}$. In conclusione solo uno degli archi ${\displaystyle (v_{1},v_{i})}$, ${\displaystyle (v_{i-1},v_{n})}$ può esistere. Essendo le possibili scelte di ${\displaystyle i}$ pari a ${\displaystyle n-1}$ e per ogni ${\displaystyle i}$ possiamo aggiungere (al più) ${\displaystyle v_{i}}$ ai vicini di ${\displaystyle v_{1}}$ escludendo però ${\displaystyle v_{i-1}}$ ai vicini di ${\displaystyle v_{n}}$ e viceversa, abbiamo che necessariamente ${\displaystyle deg(v_{1})+deg(v_{n})\leq n-1}$. Dunque non viene soddisfatta la condizione posta dal teorema di Ore. Poiché il grado dei vertici in ${\displaystyle G}$ è minore o al più uguale a quello di ${\displaystyle H}$, la condizione del teorema di Ore non viene soddisfatta nemmeno in ${\displaystyle G}$.

Corollari

Un corollario del teorema di Ore è il teorema di Dirac che afferma che se per ogni vertice ${\displaystyle v}$ di un grafo ${\displaystyle G}$ di ${\displaystyle n\geq 3}$ vertici, vale ${\displaystyle deg(v)\geq {\frac {n}{2}}}$ allora ${\displaystyle G}$ possiede un ciclo hamiltoniano. È immediato vedere che se vale tale relazione per ogni vertice essa vale anche per due vertici ${\displaystyle v}$ e ${\displaystyle w}$ non adiacenti e in particolare si ha ${\displaystyle deg(v)+deg(w)\geq {\frac {n}{2}}+{\frac {n}{2}}=n}$. La condizione di Ore è quindi soddisfatta.

Bibliografia

• Andrian Bondy M. Ram Murty, Graph Theory, Springer, 2011, ISBN 978-1-84628-969-9.