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= \left( V, E \right)$ 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'= \left( V \setminus U, E \right)$ 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' \left( V \setminus U, E \right)$ vztah $K \le |U|$ zřejmě musí platit.

Implikace "doleva"

• TODO: dukaz