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.

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

Per prima cosa scriviamo la condizione:

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

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

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

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

• J. A. Bondy e U. S. R. Murty, Graph theory with applications, New York, American Elsevier Pub. Co., 1976, ISBN 0-444-19451-7.
• László Lovász e M. D. Plummer, Matching theory, Amsterdam, North-Holland, 1986, ISBN 0-444-87916-1.

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

Portale Matematica: accedi alle voci di Teknopedia che trattano di Matematica