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!