---

Claim. Every $4$-regular graph contains a $3$-regular subgraph, and for every $r\ge3$ every $r$-regular graph contains a $3$-regular subgraph. These are Theorems 1 and 2 of V. A. Tashkinov, Regular subgraphs of regular graphs, Dokl. Akad. Nauk SSSR 265 (1982), no. 1, 43--44 (in Russian; English translation Soviet Math. Dokl. 26 (1982), 37--38), read and paged by the corpus at Theorem 1 and Theorem 2. Theorem 1 is the first question of Problem 715, the Berge--Sauer conjecture. Theorem 2 answers the second question in Tashkinov's formulation, which the problem page records (an $r_0$ such that every $r\ge r_0$ works), with $r_0=3$, where $r=3$ is trivial and $r=4$ is Theorem 1 (read literally, the question already holds at $r=3$); the note introduces Theorem 2 as the solution of the problem Erdős posed in his 1981 Combinatorica paper. The note was presented to the Academy on 4 February 1982 and received on 19 February 1982; this page is dated by the presentation, the earliest dated posting of the result, since the issue carries no day of publication.

Acceptance. The note is a publication in the Academy's Doklady, communicated by an academician, with reviews in Mathematical Reviews and zbMATH (MR 0671639, Zbl 0512.05056 per the Math-Net.Ru record) and an English translation in Soviet Mathematics Doklady, and the site's curator, Thomas Bloom, marks the problem proved and credits the note. An independent attestation by named experts is in print: the refereed note of Alon, Friedland and Kalai, Every 4-regular graph plus an edge contains a 3-regular subgraph, J. Combin. Theory Ser. B 37 (1984), 92--93, which the corpus reads and pages at its source card, says of the Berge--Sauer conjecture that it "has recently been proved" and cites Tashkinov for the proof. The basis of this page is the statements of Theorems 1 and 2 in the Russian text, in the corpus's own translation, and the structure of the proof route: a Doklady note prints sketches, and none is checked. The English translation is not compared. The acceptance recorded here rests on the publication, the printed attestation and the curator's credit, not on a local review.

Related result. The Alon--Friedland--Kalai note's own theorem, paged at its theorem, gives a $3$-regular subgraph in every $4$-regular loopless multigraph plus one edge. The site's commentary deduces from it that every $r$-regular graph with $r\ge5$ has a $3$-regular subgraph, which would answer Tashkinov's formulation with $r_0=5$; the note prints no such sentence. The problem's standing rests on Tashkinov's two theorems.