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ů. +more 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"

Kategorie:Grafové pojmy Kategorie:Matematické věty a důkazy