Теорема Татта о паросочетаниях — теоретико-графовое утверждение, дающее необходимое и достаточное условие на существование совершенного паросочетания в графе; обобщает теорему о свадьбах для двудольных графов и является частным случаем формулы Татта — Бержа.
Утверждение теоремы: граф имеет совершенное паросочетание тогда и только тогда, когда для каждого подмножества вершин подграф, индуцированный , имеет не более связных компонент с нечётным числом вершин.
Установлена Уильямом Таттом в 1947 году.
Для связных бесконечных графов с конечными степенями всех вершин имеет место следующее обобщение: совершенное паросочетание на таком графе существует тогда и только тогда, когда нельзя выбрать конечное подмножество вершин такое, что в графе компонент с конечным нечётным числом вершин больше .
Примечания
Литература
</
Категория:Теоремы теории графов