Теорема Холла — формулировка и доказательство

Вообще говоря, задачи 1, 2 и 3 — это одна и та же задача. Действительно, задача 1 сводится к задаче 3 следующим образом. V ₁ — множество юношей, V ₂ — множество девушек, рёбра — знакомства юношей с девушками. В таком случае совершенное паросочетание — искомый набор свадеб. Задача 2 сводится к задаче 3 следующим образом. Положим V ₁: = S, V₂: = Е, ребро (S_k,e_i) существует, если . В таком случае совершенное паросочетание — искомая трансверсаль. Таким образом, задачи 1, 2 и 3 имеют общий ответ: в том и только том случае, когда

что устанавливается следующей теоремой.

Пусть G (V, Е) – граф, A – подмножество вершин V, т.е. , тогда пусть обозначим через - множество всех вершин, смежных с вершинами из A.

Теорема (Холла). Пусть G (V ₁, V ₂, Е) — двудольный граф. Совершенное паросочетание из V ₁ в V ₂ существует тогда и только тогда, когда ().

Доказательство. Пусть существует совершенное паросочетание из V ₁ в V ₂. Тогда в входит |А| вершин из V₂, парных к вершинам из множества А, и, возможно, еще что-то. Таким образом, |А| .

Добавим в G две новые вершины и и v, так что вершина и смежна со всеми вершинами из V₁, а вершина v смежна со всеми вершинами из V₂. Совершенное паросочетание из V ₁ в V ₂ существует тогда и только тогда, когда существуют | V ₁| вершинно-непересекающихся простых (и, v)-цепей (рис. 37). Ясно, что |Р(u, v)| (так как V₁ разделяет вершины и и v).

По теореме Менгера max|P(и, v)| = min|R(и, v)| = |R|, где R — наименьшее мно­жество, разделяющее вершины и и v. Имеем . Покажем, что . Пусть , , . Тогда . Действительно, если бы , то существовал бы «обходной» путь (и, v₁,v₂,v) (см. рис. 37) и S не было бы разделяющим множеством для и и v. Имеем: . Следовательно, .

Рис. 37. К доказательству теоремы Холла