Tutt illesztési tétele

A Tutt-féle illesztési tétel egy gráfelméleti állítás, amely szükséges és elégséges feltételt ad a tökéletes illeszkedés gráfban való létezéséhez ; általánosítja az esküvőtételt kétrészes gráfokra, és a Tatta-Berge képlet speciális esete .

Tétel állítása: egy gráfnak akkor és csak akkor van tökéletes illeszkedése , ha a csúcsok minden részhalmazára a - által indukált részgráfnak nincs több páratlan számú csúcsú összekapcsolt komponense . $G=(V,E)$ $U\subseteq V$ $V\setminus U$ $|U|$

Telepítette : William Tutt .

Irodalom

Bondy, JA Gráfelmélet alkalmazásaival (neopr.) . New York: Amerikai Elsevier Pub. Co., 1976. - ISBN 0-444-19451-7 .
Lovasz, László. Matching theory (neopr.) . - Amszterdam: Észak-Hollandia, 1986. - ISBN 0-444-87916-1 .