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 má perfektní párování právě tehdy, když pro každou podmnožinu vrcholů platí, že počet komponent souvislosti s lichým počtem vrcholů v indukovaném podgrafu je menší nebo roven kardinalitě .
Důkaz
Implikace "doprava" Vyberme si nějakou podmnožinu vrcholů a odstraňme ji z spolu se všemi hranami, které mají alespoň jeden konec v . Nyní se podívejme na všechny vzniklé komponenty souvislosti s lichým počtem vrcholů. Jelikož před odebráním měl perfektní párování, musela z každé této komponenty vést alespoň jedna hrana k nějakému vrcholu v (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í 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 – počet lichých komponent podgrafu vztah zřejmě musí platit.
Implikace "doleva"
Kategorie:Grafové pojmy Kategorie:Matematické věty a důkazy