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?

Posted on Categories proxies

Upper bound on the length of chordless cycles in d-regular graphs

Given a $$d$$-regular graph with $$n$$ vertices is there a known (non-trivial) upper bound on the length of chordless cycles in it (presumably as a function of $$d$$ and $$n$$)? I wasn’t able to find anything after some online searches. Thank you.