Мы знаем стандартный алгоритм поиска максимального соответствия в общем графе.
https://en.wikipedia.org/wiki/Blossom_algorithm
Что я пытаюсь понять, так это то, что нужно обращаться с цветением отдельно?
Я думаю, что достаточно найти путь дополнения и дополнить его. Он также работает с нечетным циклом.