2
$\begingroup$

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?

Improve this question
$\endgroup$
8
  • $\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, 2019 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, 2019 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, 2019 at 16:31
  • $\begingroup$ @YuvalFilmus I have edited the question. Have a look now. $\endgroup$
    – RandomPerfectHashFunction
    Oct 13, 2019 at 17:52
  • $\begingroup$ Your argument doesn’t work. I already gave you a counterexample. $\endgroup$
    – Yuval Filmus
    Oct 13, 2019 at 18:07

1 Answer 1

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$
5
  • $\begingroup$ The question you refer to is about 1-factors... The OP question is about subgraphs - more general case $\endgroup$
    – HEKTO
    Oct 13, 2019 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, 2019 at 18:41
  • $\begingroup$ Subgraphs can have less vertices $\endgroup$
    – HEKTO
    Oct 13, 2019 at 18:42
  • $\begingroup$ Factors have the same vertex set $\endgroup$
    – HEKTO
    Oct 13, 2019 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, 2019 at 18:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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