Regular subpseudographs of regular pseudographs (Q1813087)

It is easily seen that each \(r\)-regular graph has an \((r-1)\)-regular subgraph for \(1\leq r\leq 3\). The well-known Berge conjecture that each 4- regular graph has a 3-regular subgraph has been proved in author's paper [Math. Notes 36, 612-623 (1984; Zbl 0558.05051); translation from Mat. Zametki 36, No. 2, 239-259 (1984)]. It will be proved in this note that for arbitrary \(r\geq 5\) there exists an \(r\)-regular graph that does not have any \((r-1)\)-regular subgraph. The following natural question arises: For what \(r\) and \(\rho\) does each \(r\)-regular graph have a \(\rho\)-regular subgraph? (For example, Erdős has asked: For what \(r\) each \(r\)-regular graph has a 3-regular subgraph?) In the present note we give an exhaustive solution of this problem for the class of regular pseudographs.