Теорема Мендельсона — Далмейджа
Теорема Мендельсона — Далмейджа — утверждение о свойстве паросочетаний в двудольных графах: если для двудольного графа  с подмножествами вершин  и  существуют паросочетания  и  такие, что  насыщает , а  насыщает , то существует паросочетание , которое насыщает одновременно множества  и  (паросочетание  насыщает подмножество вершин, если для любой вершины в этом подмножестве существует ребро из , которое инцидентно этой вершине).

Доказана  и Ллойдом Далмейджем в 1958 году. Следствие из теоремы даёт один из алгоритмов построения оптимальной рёберной раскраски двудольного графа (или, что то же самое, разбиения множества рёбер двудольного графа на наименьшее число паросочетаний).

Следствия 
В двудольном графе существует паросочетание, насыщающее все вершины максимальной степени. Действительно, если максимальная степень вершины в двудольном графе равняется , то можно взять в качестве множества  все вершины левой доли со степенью , а в качестве множества  — все вершины правой доли со степенью  (одно из множеств  и  может быть и пустым); из теоремы Холла следует, что существуют паросочетания  и , насыщающие множества  и  соответственно. Значит, по теореме Мендельсона — Далмейджа, существует и паросочетание , насыщающее все вершины степени .

Множество рёбер двудольного графа с максимальной степенью вершины  можно разбить на  паросочетаний, или, иными словами, для рёберной раскраски этого графа необходимо и достаточно  цветов (этот результат впервые получен Кёнигом). Поскольку в графе существует паросочетание, насыщающее все вершины степени , то удаление из графа всех рёбер этого паросочетания даёт граф с максимальной степенью вершин ; эту процедуру можно повторить до тех пор, пока в графе не останется рёбер.

Алгоритм и вычислительная сложность 
Доказательство теоремы Мендельсона — Далмейджа и следствий из неё фактически является алгоритмом разбиения рёбер двудольного графа на наименьшее число паросочетаний.

Алгоритм выполняет  шагов, на каждом нужно построить паросочетания  и  (это можно сделать алгоритмом Хопкрофта — Карпа за время ) и паросочетание  (это можно сделать за время ). Итоговая сложность работы алгоритма — .

Примечания

Ссылки 
 
 
 

Теоремы теории графов
Комбинаторика