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

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

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

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

Обозначим за [math]o(G)[/math] количество нечетных компонент связности в графе [math]G[/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]