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!

  • $\begingroup$ Other sources give the name as Taskinov, although I would transliterate it as Tashkinov. $\endgroup$ Oct 12, 2018 at 18:43
  • 3
    $\begingroup$ 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. $\endgroup$
    – Mike
    Oct 13, 2018 at 17:13
  • 1
    $\begingroup$ @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? $\endgroup$
    – Prism
    Oct 15, 2018 at 7:14
  • 1
    $\begingroup$ @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$. $\endgroup$
    – Mike
    Oct 15, 2018 at 17:18
  • 2
    $\begingroup$ @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. $\endgroup$
    – Yixin Cao
    May 30, 2020 at 3:52


You must log in to answer this question.

Browse other questions tagged .