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?

  • $\begingroup$ 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. $\endgroup$ – Yuval Filmus Oct 13 '19 at 15:57
  • $\begingroup$ Your claim is also not true, since you need the graph to be simple. Consider what happens if $G$ is the complete graph. $\endgroup$ – Yuval Filmus Oct 13 '19 at 16:01
  • $\begingroup$ Oh I'm really sorry. I've been ambiguous about whats the opposite of what. Let me edit the question. $\endgroup$ – RandomPerfectHashFunction Oct 13 '19 at 16:31
  • $\begingroup$ @YuvalFilmus I have edited the question. Have a look now. $\endgroup$ – RandomPerfectHashFunction Oct 13 '19 at 17:52
  • $\begingroup$ Your argument doesn’t work. I already gave you a counterexample. $\endgroup$ – Yuval Filmus Oct 13 '19 at 18:07

Your conjecture is false. There are regular graphs with an even number of vertices yet without a 1-regular subgraph. See this question on Mathematics.

The complement of such a graph gives a counterexample to your claim that you can always add a perfect matching to increase the regularity (when the number of vertices is even).

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.

| cite | improve this answer | |
  • $\begingroup$ The question you refer to is about 1-factors... The OP question is about subgraphs - more general case $\endgroup$ – HEKTO Oct 13 '19 at 18:40
  • $\begingroup$ @HEKTO A $d$-factor is a $d$-regular subgraph (on the same set of vertices). That's the definition. $\endgroup$ – Yuval Filmus Oct 13 '19 at 18:41
  • $\begingroup$ Subgraphs can have less vertices $\endgroup$ – HEKTO Oct 13 '19 at 18:42
  • $\begingroup$ Factors have the same vertex set $\endgroup$ – HEKTO Oct 13 '19 at 18:43
  • $\begingroup$ 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). $\endgroup$ – Yuval Filmus Oct 13 '19 at 18:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.