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

Тождества Галлаи в теории графов — это соотношения между численными характеристиками произвольного графа $G$: числом независимости $\alpha (G)$, числом вершинного покрытия $\tau (G)$, числом паросочетания $\nu (G)$ и числом рёберного покрытия $\rho (G)$.

Тождества опубликованы венгерским математиком Тибором Галлаи в 1959 году. Сам Галлаи утверждал, что получил эти результаты ещё в 1932 году, при этом полагая, что в то время Кёнигу о них уже было известно.

Первое тождество Галлаи

В любом графе $G=(V,E)$ выполняется соотношение $\alpha (G)+\tau (G)=|V|$.

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

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

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

Второе тождество Галлаи

В любом графе $G=(V,E)$, не содержащем изолированных вершин (т.е. вершин со степенью 0), выполняется соотношение $\nu (G)+\rho (G)=|V|$.

Примечание:

Если в графе есть хоть одна изолированная вершина, то рёберного покрытия не существует, следовательно, число рёберного покрытия $\rho (G)$ не определено.

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

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

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

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