Тождества Галлаи

Пусть ${\displaystyle T}$ — наименьшее вершинное покрытие в графе ${\displaystyle G}$. Рассмотрим множество вершин ${\displaystyle V\setminus T}$. Поскольку любое ребро ${\displaystyle e\in E}$ инцидентно хотя бы одной вершине из множества ${\displaystyle T}$, ни одно ребро не соединяет две вершины из множества ${\displaystyle V\setminus T}$. Следовательно, ${\displaystyle V\setminus T}$ является независимым множеством вершин в графе ${\displaystyle G}$, и его размер ${\displaystyle |V|-\tau (G)}$ не превосходит размера наибольшего независимого множества вершин, то есть, ${\displaystyle \alpha (G)}$.

Рассмотрев наибольшее независимое множество вершин в графе ${\displaystyle G}$ и проделав такое же рассуждение в обратную сторону, получим неравенство ${\displaystyle |V|-\alpha (G)\geq \tau (G)}$, что в совокупности с первым неравенством даёт ${\displaystyle \alpha (G)+\tau (G)=|V|}$.

Рассмотрим наименьшее рёберное покрытие ${\displaystyle R}$ в графе ${\displaystyle G}$. Если бы ${\displaystyle R}$ содержало циклы, то можно было бы удалить одно из рёбер цикла, получив рёберное покрытие размера на единицу меньше. Следовательно, ${\displaystyle R}$ образует лес на множестве вершин ${\displaystyle V}$, и выполняется равенство ${\displaystyle |V|-|R|=K}$, где ${\displaystyle K}$ — количество компонент связности в этом лесе. Взяв из каждой компоненты связности по одному ребру, получим паросочетание в графе ${\displaystyle G}$ размера ${\displaystyle |V|-\rho (G)}$. Следовательно, размер наибольшего паросочетания ${\displaystyle \nu (G)\geq |V|-\rho (G)}$.

Далее, рассмотрим наибольшее паросочетание ${\displaystyle N}$ в графе ${\displaystyle G}$. Оно насыщает ${\displaystyle 2\cdot \nu (G)}$ вершин графа ${\displaystyle G}$, следовательно, ${\displaystyle |V|-2\cdot \nu (G)}$ вершин остаются ненасыщенными. Возьмём для каждой ненасыщенной вершины графа по одному ребру, обозначим множество таких рёбер ${\displaystyle N_{1}}$. Если хотя бы одно ребро из ${\displaystyle N_{1}}$ соединяло бы сразу две ненасыщенные вершины, это ребро можно было бы добавить в паросочетание ${\displaystyle N}$, что невозможно, поскольку это наибольшее паросочетание. Значит, во множестве ${\displaystyle N_{1}}$ ровно ${\displaystyle |V|-2\cdot \nu (G)}$ рёбер. Множество ${\displaystyle N\cup N_{1}}$ является рёберным покрытием в графе ${\displaystyle G}$, следовательно, его размер ${\displaystyle |V|-\nu (G)}$ не меньше размера наименьшего рёберного покрытия ${\displaystyle \rho (G)}$.

Объединив неравенства ${\displaystyle \nu (G)\geq |V|-\rho (G)}$ и ${\displaystyle |V|-\nu (G)\geq \rho (G)}$, получим искомое тождество ${\displaystyle \nu (G)+\rho (G)=|V|}$.