Теорема Татта о паросочетаниях

Теорема Татта о паросочетаниях — теоретико-графовое утверждение, дающее необходимое и достаточное условие на существование совершенного паросочетания в графе; обобщает теорему о свадьбах для двудольных графов и является частным случаем формулы Татта — Бержа.

Утверждение теоремы: граф $G=(V,E)$ имеет совершенное паросочетание тогда и только тогда, когда для каждого подмножества вершин $U\subseteq V$ подграф, индуцированный $V\setminus U$, имеет не более $|U|$ связных компонент с нечётным числом вершин.

Установлена Уильямом Таттом.

Литература

• Шаблон:Книга
• Шаблон:Книга