Линейный алгоритм извлечения почти регулярного остовного подграфа из почти регулярного графа

Рассматриваются почти $d$-регулярные ненаправленные графы, т.е. такие, в которых все степени равны $d$ или $d-1$. Известно, что для произвольного $d'\le d$ в любом почти $d$-регулярном графе существует почти $d'$-регулярный остовный подграф. Приводится алгоритм, реализующий этот выбор за оптимальное линейное время.