максимизировать
при условии
где
т. e. просто множество ребер, инцидентных вершине 
и
Как уже говорилось выше, условия целочисленности (12.13) не являются излишними в случае существования в графе циклов с нечетным числом ребер. Однако Эдмондс [10, 11, 12] показал, что эти условия могут быть заменены системой линейных ограничений, и доказал следующую теорему.
Теорема 5 [11]. Для любого графа выпуклая оболочка решений (12.12) и (12.13) является полиэдром, определенным соотношениями (12.12), и, кроме того
(i) для каждого подмножества 
с X, содержащего нечетное число вершин (скажем, 
с некоторым положительным целым 
следует добавить ограничения
где 
множество ребер порожденного подграфа 
и
(ii) следует добавить ограничения 
для (12.15) всех 
Ясно, что любое паросочетание из 
удовлетворяет ограничениям (12.14). Не очевидно только, что эти ограничения достаточны. Мы обоснуем их достаточность конструктивно, предъявив совершенное паросочетание из 
являющееся решением задачи линейного программирования (12.11), (12.12), (12.14) и (12.15) с любым заданным вектором 
реберных весов.
Обозначим сформулированную выше задачу линейного программирования через 
Двойственной задачей к 
будет [8] следующая:
минимизировать
при условии
и
Таким образом, с каждой вершиной 
из 
связана некоторая переменная 
а с каждым множеством 
состоящим из нечетного числа вершин, связана переменная 
В ограничениях 
вес ребра а, вида 
семейство подмножеств 
содержащих как 
так и 
В соответствии с теоремой двойственности линейного программирования вектор 
максимизирует 
при условиях (12.12), (12.14) и (12.15), а вектор 
минимизирует и при условиях (12.17) и (12.18) тогда и только тогда, когда
(i) для каждого 
или 
или же в соответствующем ограничении (12.14) имеет место равенство;
(ii) для каждого 
или 
или же в соответствующем ограничении (12.17) имеет место равенство.
Мы дадим доказательство теоремы 5, описав процедуру, позволяющую находить совершенное паросочетание 
(и, следовательно, вектор 
а также вектор 
удовлетворяющий условиям (12.17) и (12.18) и условиям двойственности 
Таким образом будет доказано, что 
оптимальное паросочетание.
ребрам которого 
приписаны веса 
В этом разделе мы исследуем задачу нахождения совершенного паросочетания (т. е. паросочетания, в котором каждая вершина «сочетается» с некоторой другой вершиной), имеющего максимальный вес. Эта задача определяется соотношениями (12.2) — (12.4) с той лишь разницей, что неравенство в (12.3) должно быть заменено равенством. Во введении было объяснено, как задачи с ограничениями в виде равенств или неравенств можно сделать эквивалентными путем добавления ребер с весом 
и искусственной вершины — в случае нечетного числа вершин. Таким образом, рассматриваемая ЗМП формулируется так:
