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

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

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

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

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

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

Множество Татта графа [math]\mathbb{G}[/math] — множество [math]S \subset \mathbb{V_{G}}[/math], для которого выполнено условие: [math]o(\mathbb{G} \setminus S) \gt \left\vert S \right\vert[/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]\mathbb{G}[/math] существует полное паросочетание [math]\Leftrightarrow[/math] [math]\forall S \subset \mathbb{V_\mathbb{G}}[/math] выполнено условие: [math]o(\mathbb{G} \setminus S) \leqslant \left\vert S \right\vert[/math]

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

[math]\triangleright[/math]

[math]\Rightarrow[/math] Рассмотрим [math]M[/math] — полное паросочетание в графе [math]\mathbb{G}[/math] и множество вершин [math]S \subset \mathbb{V_\mathbb{G}}[/math]. Одна из вершин каждой нечетной компоненты связности графа [math] \mathbb{G} \setminus S[/math] соединена ребром паросочетания [math]M[/math] с какой-то вершиной из [math]S[/math]. Иначе мы не сможем покрыть паросочетанием все вершины этой компоненты связности и получим противоречие с тем, что полное паросочетание существует по условию теоремы. Таким образом, получаем, что [math]o(\mathbb{G} \setminus S) \leqslant \left\vert S \right\vert[/math]. [math]\Leftarrow[/math] Пусть для графа [math]\mathbb{G}[/math] выполнено, что [math]o(\mathbb{G} \setminus S) \leqslant \left\vert S \right\vert[/math], но полного паросочетания в этом графе не существует. Рассмотрим граф [math]\mathbb{G'}[/math] и множество вершин [math]U[/math] (из леммы). Так как число нечетных компонент не увеличивается при добавлении новых ребер, то [math]\forall S \subset \mathbb{V_\mathbb{G}}[/math] выполнено, что [math]o(\mathbb{G'} \setminus S) \leqslant o(\mathbb{G} \setminus S) \leqslant \left\vert S \right\vert[/math]. По лемме, доказанной выше: [math]\mathbb{G'} \setminus U[/math] — объединение несвязных полных графов. Очевидно, что в каждой четной компоненте связности графа [math]\mathbb{G'} \setminus U[/math] мы можем построить полное паросочетание. В каждой нечетной компоненте этого графа построим паросочетание, которое покрывает все вершины кроме одной, оставшуюся непокрытой вершину, соединим с какой-то вершиной множества [math]U[/math]. При этом мы будем использовать различные вершины из [math]U[/math], это возможно, так как [math]o(G' \setminus U) \leqslant \left\vert U \right\vert[/math]. Если все вершины множества [math]U[/math] оказались покрытыми, то мы получили полное паросочетание в графе [math]\mathbb{G'}[/math]. Противоречие, так как по построению в [math]\mathbb{G'}[/math] нет полного паросочетания. Значит, в [math]U[/math] осталось какое-то количество непокрытых вершин, при этом их четное число, потому что число вершин в [math]\mathbb{G'}[/math] четно, так как [math]o(\mathbb{G'} \setminus \varnothing) \leqslant \left\vert \varnothing \right\vert = 0[/math] и уже покрыто паросочетанием четное число вершин. Так как в множество [math]U[/math] входят вершины, которые в [math]\mathbb{G'}[/math] смежны со всеми остальными, то мы сможем разбить оставшиеся вершины на пары и покрыть их паросочетанием. Таким образом, получили в [math]\mathbb{G'}[/math] полное паросочетание, что противоречит тому, как мы задали этот граф изначально. Значит, предположение не верно, и в [math]\mathbb{G}[/math] существует полное паросочетание.

[math]\triangleleft[/math]