# Existence of d-regular subgraphs in a k-regular graph

The claim is as follows: Let's say we have a $$k$$-regular simple undirected graph $$G$$ on $$n$$ vertices. Then, does $$G$$ then always have a $$d$$-factor for all $$d$$ satisfying $$1 \le d \lt k$$ and $$dn$$ being even.

I think its true, since we can construct a

• $$k+1$$-regular graph from $$G$$ by adding $$\frac{n}{2}$$ edges for even $$n$$ or
• $$k+2$$-regular graph from $$G$$ by adding $$n$$ edges for odd $$n$$

And the converse for the above. We can construct a $$k$$-regular graph on $$n$$ vertices by

• removing $$\frac{n}{2}$$ edges from a $$k+1$$-regular graph for even $$n$$.
• removing $$n$$ edges from a $$k+2$$-regular graph for odd $$n$$.

Hence, using the converse argument, we can say that the original claim is true, since from a $$k$$-regular graph $$G$$ we can construct

• $$1$$-factor, $$2$$-factor, ... $$k-1$$-factor for even $$n$$ or
• $$2$$-factor, $$4$$-factor, ... $$k-2$$-factor for odd $$n$$

Is my argument correct or is there any flaw in this argument?

• Hence, the opposite should also be true. Why? There are a lot of statements of the type $A \Rightarrow B$ in which the converse $B \Rightarrow A$ is false. For example, if $a$ is positive then so is $a^2$, but the converse doesn't hold. – Yuval Filmus Oct 13 '19 at 15:57
• Your claim is also not true, since you need the graph to be simple. Consider what happens if $G$ is the complete graph. – Yuval Filmus Oct 13 '19 at 16:01
• Oh I'm really sorry. I've been ambiguous about whats the opposite of what. Let me edit the question. – RandomPerfectHashFunction Oct 13 '19 at 16:31
• @YuvalFilmus I have edited the question. Have a look now. – RandomPerfectHashFunction Oct 13 '19 at 17:52
• Your argument doesn’t work. I already gave you a counterexample. – Yuval Filmus Oct 13 '19 at 18:07

In the bipartite case, however, your conjecture is true. Any $$k$$-regular bipartite graph can be decomposed into $$k$$ perfect matchings. This follows from Hall's theorem.
• @HEKTO A $d$-factor is a $d$-regular subgraph (on the same set of vertices). That's the definition. – Yuval Filmus Oct 13 '19 at 18:41
• Reading the post, it seems clear that the OP is after subgraphs obtained just by removing edges. For example, otherwise there is no reason to restrict to even $dn$ (I'll let you figure out some other hints). – Yuval Filmus Oct 13 '19 at 18:48