Teorema di Tutte
# Teorema di Tutte

Nella disciplina matematica della teoria dei grafi il teorema di Tutte, che prende nome da William Thomas Tutte, è una caratterizzazione dei grafi con accoppiamenti perfetti. È una generalizzazione del teorema dei matrimoni ed è un caso particolare della formula di Tutte-Berge.

## Teorema di Tutte

Un grafo, $\scriptstyle G=(V,E)$, ha un accoppiamento perfetto se e solo se per ogni sottoinsieme $\scriptstyle U$ di $\scriptstyle V$, il sottografo indotto da $\scriptstyle V-U$ ha al massimo $\scriptstyle |U|$ componenti connesse con un numero dispari di vertici.

## Dimostrazione

Per prima cosa scriviamo la condizione:

    $(*)\qquad \forall U\subseteq V,\quad o(G-U)\leq |U|$

Necessità di (∗): Si consideri un grafo $\scriptstyle G$, con un accoppiamento perfetto. Sia $\scriptstyle U$ un sottoinsieme arbitrario di $\scriptstyle V$. Si elimini $\scriptstyle U$. Sia $\scriptstyle C$ una componente dispari arbitraria in $\scriptstyle G-U$. Poiché $\scriptstyle G$ aveva un accoppiamento perfetto, almeno un vertice in $\scriptstyle C$ deve essere accoppiato a un vertice in $\scriptstyle U$. Quindi ciascuna componente dispari ha almeno un vertice accoppiato con un vertice in $\scriptstyle U$. Poiché ciascun vertice in $\scriptstyle U$ può essere in questa relazione con al massimo una componente connessa (in quanto essa viene accoppiata al massimo una sola volta in un accoppiamento perfetto), $\scriptstyle o(G-U)\leq |U|$.

Sufficienza di (∗): Sia $\scriptstyle G$ un grafo arbitrario che soddisfa (∗). Si consideri l'espansione di $\scriptstyle G$ a $\scriptstyle G*\$, un grafo massimamente imperfetto, nel senso che $\scriptstyle G$ è un sottografo ricoprente di $\scriptstyle G*\$, ma aggiungere uno spigolo a $\scriptstyle G*\$ darà come risultato un accoppiamento perfetto. Osserviamo che $\scriptstyle G*\$ soddisfa anche la condizione (∗) poiché $\scriptstyle G*\$ è $\scriptstyle G$ con spigoli aggiuntivi. Sia $\scriptstyle U$ l'insieme dei vertici di grado $\scriptstyle |V|-1$. Eliminando $\scriptstyle U$, otteniamo un'unione disgiunta di grafi completi (ciascuna componente è un grafo completo). Si può ora definire un accoppiamento perfetto accoppiando indipendentemente ogni componente pari, e accoppiando un vertice di una componente dispari $\scriptstyle C$ a un vertice in $\scriptstyle U$ e i vertici rimanenti in $\scriptstyle C$ tra loro stessi (dal momento che rimane un numero pari di essi questo è possibile). I vertici rimanenti in $\scriptstyle U$ possono essere accoppiati in modo simile, in quanto $\scriptstyle U$ è completo.

Questa dimostrazione non è completa. Eliminare $\scriptstyle U$ può creare un'unione disgiunta di grafi completi, ma il caso in cui ciò non accade è la parte più interessante e difficile della dimostrazione.

