Problem 715

Does every regular graph of degree $4$ contain a regular subgraph of degree $3$ ? Is there any $r$ such that every regular graph of degree $r$ must contain a regular subgraph of degree $3$ ?

Source: erdosproblems.com/715

Graph theory

Wiki page

Status

SolvedProved

An accepted solution exists. The statement is true.

Proved. Both questions are answered in the affirmative by Tashkinov's note [Ta82] (Dokl. Akad. Nauk SSSR 265 (1982), no. 1, 43--44, in Russian; the site's key is its English translation in Soviet Math. Dokl. 26 (1982), 37--38), in this page's translation: Theorem 1 (Tashkinov 1982), "Every 4-regular graph has a 3-regular subgraph", and Theorem 2 (Tashkinov 1982), "For every $r\ge3$ every $r$ -regular graph has a 3-regular subgraph", which the note presents as the solution of the problem Erdős posed in [Er81]; the claim page Tashkinov 1982 records the result, its scope and its acceptance evidence, from which the frontmatter standing is derived. The refereed note of Alon, Friedland and Kalai [AFK84] attests the first theorem ("the well known Berge--Sauer conjecture [2], which has recently been proved [4]", [4] = Tashkinov) and proves that a 4-regular loopless multigraph plus one edge contains a 3-regular subgraph (theorem). Tashkinov's proofs are sketches and were not checked; the English translation was not compared.

Ta82: Tashkinov, V. A., Однородные части однородных графов (Regular subgraphs of regular graphs). Dokl. Akad. Nauk SSSR 265 (1982), no. 1, 43--44 (in Russian; presented 4 February 1982, received 19 February 1982; MR 0671639 and Zbl 0512.05056 per the Math-Net.Ru record). English translation: Soviet Math. Dokl. 26 (1982), 37--38, the site's reference text; not held. Theorems 1--3, p. 43; Theorem 5 and the proof pointers, p. 44. Library home: Tashkinov 1982 (Math-Net.Ru's scan); paged at Tashkinov 1982, Theorem 1 (p. 43) and Tashkinov 1982, Theorem 2 (p. 43).
AFK84: Alon, N., Friedland, S. and Kalai, G., Every 4-regular graph plus an edge contains a 3-regular subgraph. J. Combin. Theory Ser. B 37 (1984), no. 1, 92--93, doi:10.1016/0095-8956(84)90048-0 (received 25 July 1983; Crossref record accessed; the site's reference text gives the journal, year and pages without the volume). Library home: Alon and Kalai 1984; paged at Alon and Kalai 1984, Theorem (p. 92).
AFK84b: Alon, N., Friedland, S. and Kalai, G., Regular subgraphs of almost regular graphs. J. Combin. Theory Ser. B 37 (1984), no. 1, 79--91, doi:10.1016/0095-8956(84)90047-9 (Crossref record accessed). Not held; the note's reference [1], where "more general graph theoretical results" are proved.
Er75: Erdős, P., Some recent progress on extremal problems in graph theory. Congr. Numer. XIV (1975), 3--14; printed p. 11 (the article's pages carry no printed page numbers). Library home: Erdős 1975; the passage is paged at Erdős 1975, Conjecture (Section 3, printed p. 11 = PDF p. 9).
Er81: Erdős, P., On the combinatorial problems which I would most like to see solved. Combinatorica 1 (1981), 25--42; Part III, item 3, p. 7 of the retyped copy, which has its own pagination. Library home: Erdős 1981.
CFST79: Chvátal, V., Fleischner, H., Sheehan, J. and Thomassen, C., J. Graph Theory 3 (1979), p. 371, as Tashkinov's reference [4] cites it (no title printed there); the Berge--Sauer conjecture for graphs with cyclic edge connectivity at least 10, per Tashkinov's introduction. Not held.
BoMu76: Bondy, J. A. and Murty, U. S. R., Graph Theory with Applications, Macmillan (1976), p. 246, the source [AFK84] cites for the Berge--Sauer conjecture. Not held.

Problem 715

Status

Proof claims

Discussion