В доказательство рассмотрим следующий алгоритм поиска такой раскраски:
1) # Для начала сделаем доли графа одинаковыми по размеру, дополнив меньшую из долей необходимым количеством [[Основные определения теории графов#isolated_vertex | изолированных вершин]] 2) # Следующим жадным алгоритмом сделаем его <tex>\Delta(G)-</tex>-регулярным: пока граф не регулярный возьмём вершину левой доли степени меньше <tex>\Delta(G)</tex> и аналогичную вершину правой доли. Соединим их ребром 3) # Мы получили регулярный двудольный граф с равными доля. По нашей лемме в таком графе есть совершенное паросочетание. Найдём его, например [[Алгоритм Куна для поиска максимального паросочетания | алгоритмом Куна]] , и удалим его их графа. 4) # Заметим что граф всё остался регулярным, так как степень каждой вершины уменьшилась на 1. Будем повторять процесс, пока в графе есть рёбра. 5) # По итогу мы разобьём рёбра графа на <tex>\Delta(G)</tex> совершенных паросочетаний. 6) # В конце нам остаётся каждое паросочетание покрасить в свой цвет и удалить рёбра, которых не было в изначальном графе
