Теорема Татта о существовании полного паросочетания

Определение:

Нечетная компонента связности графа [math]G[/math] — компонента связности, содержащая нечетное число вершин.

Определение:

Обозначим за [math]o(G)[/math] число нечетных компонент связности в графе [math]G[/math].

Критерий Татта

Рассмотрим [math]G'[/math] — надграф [math]G[/math], в [math]G'[/math] нет полного паросочетания, но оно появляется при добавлении любого ребра, при этом [math]\left\vert V(G) \right\vert = \left\vert V(G') \right\vert = n[/math]

Пусть [math] U = \{ v \in V: deg_{G'} (v) = n - 1 \}[/math].

Лемма:

[math]G' \setminus U[/math] — объединение несвязных полных графов.

Теорема Татта

Теорема:

В графе [math]G[/math] существует полное паросочетание [math]\Leftrightarrow[/math] [math]\forall S \subset V(G)[/math] выполнено условие: [math]o(G \setminus S) \leqslant \left\vert S \right\vert[/math]

Доказательство:

[math]\triangleright[/math]

[math]\Rightarrow[/math] Рассмотрим [math]M[/math] — полное паросочетание в графе [math]G[/math] и множество вершин [math]S \subset V(G)[/math]. Одна из вершин каждой нечетной компоненты связности графа [math] G \setminus S[/math] соединена ребром паросочетания [math]M[/math] с какой-то вершиной из [math]S[/math]. Иначе мы не сможем покрыть паросочетанием все вершины этой компоненты связности и получим противоречие с тем, что полное паросочетание существует по условию теоремы. Таким образом, получаем, что [math]o(G \setminus S) \leqslant \left\vert S \right\vert[/math]. [math]\Leftarrow[/math]

[math]\triangleleft[/math]