Tutteova věta

Tutteho věta v matematické teorii grafů charakterizuje grafy s perfektním párováním. Je pojmenována po Williamu Thomasovi Tutteovi. Jedná se o zobecnění Hallovy věty.

Znění

Graf $G=(V,E)$ má perfektní párování právě tehdy, když pro každou podmnožinu vrcholů $U\subseteq V$ platí, že počet komponent souvislosti s lichým počtem vrcholů v indukovaném podgrafu $G^{\prime }=(V\setminus U,E)$ je menší nebo roven kardinalitě $U$.

Důkaz

Implikace "doprava"

Vyberme si nějakou podmnožinu vrcholů $U$ a odstraňme ji z $G$ spolu se všemi hranami, které mají alespoň jeden konec v $U$. Nyní se podívejme na všechny vzniklé komponenty souvislosti s lichým počtem vrcholů. Jelikož před odebráním $U$ měl $G$ perfektní párování, musela z každé této komponenty vést alespoň jedna hrana k nějakému vrcholu v $U$ (zřejmé z definice perfektního párování). A protože v párování musíme propojit vždy právě dva vrcholy, musí $U$ obsahovat alespoň tolik vrcholů, kolik existuje lichých komponent (všimněte si, že počítáme jenom s hranami obsaženými v nějakém perfektním párování - jiné nás nezajímají).
Čímž máme první část důkazu za sebou, neboť pro $K$ - počet lichých komponent podgrafu $G^{\prime }(V\setminus U,E)$ vztah $K\le |U|$ zřejmě musí platit.