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, $G=(V,E)$, ha un accoppiamento perfetto se e solo se per ogni sottoinsieme $U$ di $V$, il sottografo indotto da $V-U$ ha al massimo $|U|$ componenti connesse con un numero dispari di vertici.

Dimostrazione

Per prima cosa scriviamo la condizione:

$(*)\mathrm{\forall }U\subseteq V,o(G-U)\le |U|$

Necessità di (∗): Si consideri un grafo $G$, con un accoppiamento perfetto. Sia $U$ un sottoinsieme arbitrario di $V$. Si elimini $U$. Sia $C$ una componente dispari arbitraria in $G-U$. Poiché $G$ aveva un accoppiamento perfetto, almeno un vertice in $C$ deve essere accoppiato a un vertice in $U$. Quindi ciascuna componente dispari ha almeno un vertice accoppiato con un vertice in $U$. Poiché ciascun vertice in $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), $o(G-U)\le |U|$.

Sufficienza di (∗): Sia $G$ un grafo arbitrario che soddisfa (∗). Si consideri l'espansione di $G$ a $G*$, un grafo massimamente imperfetto, nel senso che $G$ è un sottografo ricoprente di $G*$, ma aggiungere uno spigolo a $G*$ darà come risultato un accoppiamento perfetto. Osserviamo che $G*$ soddisfa anche la condizione (∗) poiché $G*$ è $G$ con spigoli aggiuntivi. Sia $U$ l'insieme dei vertici di grado $|V|-1$. Eliminando $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 $C$ a un vertice in $U$ e i vertici rimanenti in $C$ tra loro stessi (dal momento che rimane un numero pari di essi questo è possibile). I vertici rimanenti in $U$ possono essere accoppiati in modo simile, in quanto $U$ è completo.

Questa dimostrazione non è completa. Eliminare $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.

Bibliografia

• Template:Cita testo
• Template:Cita libro

Voci correlate

• Accoppiamento (teoria dei grafi)
• Teorema dei matrimoni
• Teorema di Petersen