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

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

Нечетная компонента связности графа [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]\left\vert U \right\vert \ne n[/math], потому что [math]G'[/math] — не полный граф.

Лемма:

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

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

[math]\triangleright[/math]

Пусть это не так. Получили противоречие.

[math]\triangleleft[/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]G[/math] выполнено, что [math]o(G \setminus S) \leqslant \left\vert S \right\vert[/math], но полного паросочетания в этом графе не существует. Рассмотрим граф [math]G'[/math] и множество вершин [math]U[/math], которые заданы так же как в лемме. Так как число нечетных компонент не увеличивается при добавлении новых ребер, то [math]\forall S \subset V(G):[/math] [math]o(G' \setminus S) \leqslant o(G \setminus S) \leqslant \left\vert S \right\vert[/math]. По лемме, доказанной выше: [math]G' \setminus U[/math] — объединение несвязных полных графов. Очевидно, что в каждой четной компоненте связности графа [math]G' \setminus U[/math] мы можем построить полное паросочетание. В каждой нечетной компоненте этого графа построим паросочетание, которое покрывает все вершины кроме одной, оставшуюся непокрытой вершину, соединим с какой-то вершиной множества [math]U[/math]. При этом мы будем использовать различные вершины из [math]U[/math], это возможно, так как [math]o(G' \setminus U) \leqslant \left\vert U \right\vert[/math]. Осталось какое-то количество непокрытых вершин множества U. Число вершин в [math]G'[/math] четно, так как [math]o(G' \setminus \varnothing) \leqslant \left\vert \varnothing \right\vert = 0[/math], уже покрыто паросочетанием четное число вершин, значит, осталось так же четное число вершин. Так как в множество [math]U[/math] входят вершины, которые в [math]G'[/math] смежны со всеми остальными, то мы сможем разбить оставшиеся вершины на пары и покрыть их паросочетанием. Таким образом, получили в [math]G'[/math] полное паросочетание, что противоречит тому, как мы задали этот граф изначально. Значит, предположение не верно и в [math]G[/math] существует полное паросочетание.

[math]\triangleleft[/math]