Staèí provést Degree Split na~dva $2^{d-1}$-regulární grafy, na~libovolný jeden z~nich
aplikovat dal¹í Degree Split atd., a¾ se dostaneme k~$1$-regulárnímu grafu, který
je perfektním párováním v~$G$. To v¹e jsme schopni stihnout v~lineárním èase,
Staèí provést Degree Split na~dva $2^{d-1}$-regulární grafy, na~libovolný jeden z~nich
aplikovat dal¹í Degree Split atd., a¾ se dostaneme k~$1$-regulárnímu grafu, který
je perfektním párováním v~$G$. To v¹e jsme schopni stihnout v~lineárním èase,