# Every 4-regular simple graph contains a 3-regular subgraph

The following result was conjectured by Berge & Sauer, and proved by Tashkinov [T].

Theorem A. Every 4-regular simple graph contains a 3-regular subgraph.

A simple graph is the one with no loops or parallel edges. I do not have access to Tashkinov's paper, so I don't know how the proof works. On the other hand, using Combinatorial Nullstellensatz, one can show the following:

Theorem B. Every 4-regular graph plus an extra edge contains a 3-regular subgraph.

I should note that Theorem B allows the graph to have multiple edges, so in particular, you are allowed to add an extra edge to a pair of adjacent vertices (so that there are now two edges between these vertices). The proof of Theorem B is a special case of $$p=3$$ in this article here (see Theorem 2.5).

Is there any easy way to use Theorem B to prove Theorem A?

It is tempting to add a random edge $$e$$ somewhere and use Theorem B to get a 3-regular subgraph. But then we have to somehow throw out that additional edge $$e$$. We may not be able to do this, as the edge $$e$$ could be an edge appearing in the 3-regular subgraph. Is there a way to get around this, or another trick?

[T] Tashkinov. Regular subgraphs of regular graphs. Soviet Math. Dokl. 26, (1982), 37-38.

P.S. I should add that if you know how Tashkinov's original proof goes, please feel free to add it as an answer! This would be very helpful too!

• Other sources give the name as Taskinov, although I would transliterate it as Tashkinov. Oct 12, 2018 at 18:43
• Are you sure you didn't missquote. "Theorem" A would imply that every 4-regular graph has a perfect matching [make sure you see why]. However, $K_5$ is 4-regular, and does not contain a perfect matching, as it has an odd number of vertices.
– Mike
Oct 13, 2018 at 17:13
• @Mike I still don't see why the Theorem A would imply that every 4-regular graph has a perfect matching. Could you explain what is the connection between containing a 3-regular subgraph and having a perfect matching? Oct 15, 2018 at 7:14
• @Prism My apologies for whatever reason I took it to mean that the 3-regular subgraph of a 4-regular graph $G$ would be on precisely the same vertex set as $G$, instead of a possible proper subset of the vertex set of $G$.
– Mike
Oct 15, 2018 at 17:18
• @MishaLavrov The paper you mentioned is actually in English. The link you gave is to a Chinese abstract of it (kind of like Math Review), and the article can be found at caod.oriprobe.com/articles/33772845/…, which is unfortunately after a pay wall. I've get access to a copy of it. It has 25 pages, and does not seem an easy read. I'm not sure which of the two proofs is easier to follow. May 30, 2020 at 3:52