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.

Bibliografia

• 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.

Voci correlate

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