==Критерий Татта==
Рассмотрим Будем дополнять граф <tex>\mathbb{G'</tex> {{---}} надграф <tex>G</tex>ребрами, в пока не получим граф <tex>\mathbb{G'}</tex> , в котором нет полного паросочетания, но оно появляется при добавлении любого ребра, при этом <tex>\left\vert V(G) \right\vert = \left\vert V(G') \right\vert = n</tex> .
Пусть <tex> U = \{ v \in V: deg_{G'} (v) = n - 1 \}</tex>.
{{Лемма
|statement= <tex>G' \setminus U</tex> {{---}} объединение несвязных полных графов.
|proof=Пусть это не так, тогда существуют вершины <tex>x,y,z \in \mathbb{V_\mathbb{G'}} \setminus U</tex>, такие что <tex>xy, yz \in \mathbb{E_\mathbb{G'}}</tex>, но <tex>xz \notin \mathbb{E_\mathbb{G'}}</tex>. Так как <tex>y \notin U</tex>, то <tex>\exists t \notin U: yt \notin \mathbb{E_\mathbb{G'}}</tex>.
Получили В графе <tex>\mathbb{G'}+xz</tex> существует полное паросочетание <tex>M_1</tex>, так как граф <tex>\mathbb{G'}</tex> максимальный по построению. Аналогично, в графе <tex>\mathbb{G'}+yt</tex> существует полное паросочетание <tex>M_2</tex>. Так как в <tex>\mathbb{G'}</tex> нет полного паросочетания, то <tex>xz \in M_1</tex> и <tex>yt \in M_2</tex>. Возможны два случая: 1) Вершины <tex>x,z</tex> и <tex>y,t</tex> лежат в разных полных подграфах графа <tex>\mathbb{G'} \setminus U</tex>, например, в <tex>H_1</tex> и <tex>H_2</tex>, соответственно. Покроем вершины подграфа <tex>H_1</tex> паросочетанием <tex>M_2</tex>, при этом заметим, что ребро <tex>xz</tex> не входит в это паросочетание. Аналогично покроем паросочетанием <tex>M_1</tex> вершины подрафа <tex>H_2</tex> и ребро <tex>yt</tex> не войдет в это паросочетание. Если остались еще какие-то вершины, не входящие в паросочетание, то выберем для них любые ребра из паросочетаний <tex>M_1</tex> и <tex>M_2</tex>. Таким образом, мы получим полное паросочетание в графе <tex>\mathbb{G'}</tex>, что противоречит тому, как мы изначально построили этот граф. 2) Вершины <tex>x,y,z</tex> и <tex>t</tex> лежат в одном подграфе графа <tex>\mathbb{G'} \setminus U</tex>. Построим граф <tex>H</tex>, такой что <tex>\mathbb{V_\mathbb{H}}=\mathbb{V_\mathbb{G'}}</tex> и <tex>\mathbb{E_\mathbb{H}}=M_1 \oplus M_2</tex>. Получим, что вершины <tex>x,y,z</tex> и <tex>t</tex> лежат на каком-то чередующемся цикле. В силу симметричности <tex>x</tex> и <tex>z</tex> можно считать, что вершины расположены в порядке <tex>tzxy</tex>. Тогда существует путь <tex>P_1=t..zx..y</tex> и полное паросочетание в нем, но так же существует и путь <tex>P_2=t..zy..x</tex>, содержащий только ребра графа <tex>\mathbb{G'}</tex>. Значит, существует полное паросочетание на вершинах, выбранного подграфа. В остальных подграфах выберем ребра любого из паросочетаний <tex>M_1</tex> и <tex>M_2</tex>. Таким образом, получили полное паросочетание в графе <tex>\mathbb{G'}</tex>, противоречие. В каждом из возможных случаев получили предположение, значит наше начальное предположение тоже неверно и <tex>G' \setminus U</tex> {{---}} объединение несвязных полных графов, лемма доказана.
}}
Значит, в <tex>U</tex> осталось какое-то количество непокрытых вершин, при этом их четное число, потому что число вершин в <tex>\mathbb{G'}</tex> четно, так как <tex>o(\mathbb{G'} \setminus \varnothing) \leqslant \left\vert \varnothing \right\vert = 0</tex> и уже покрыто паросочетанием четное число вершин. Так как в множество <tex>U</tex> входят вершины, которые в <tex>\mathbb{G'}</tex> смежны со всеми остальными, то мы сможем разбить оставшиеся вершины на пары и покрыть их паросочетанием.
Таким образом, получили в <tex>\mathbb{G'}</tex> полное паросочетание, что противоречит тому, как мы задали этот граф изначально. Значит, начальное предположение не верно, и в <tex>\mathbb{G}</tex> существует полное паросочетание.
}}
