Let $G$ be a $(2k+1)$-regular graph on $n$ vertices. A theorem by Lovasz implies that $G$ decomposes into $\frac{1}{2}n$ disjoint paths.

Since the number of edges is $\frac{1}{2}n(2k +1)$, is it possible to require that each path in the decomposition be of size $(2k +1)$.

I found an argument for the case when the graph $G$ has a perfect matching and its girth $\geq 2k +1$. Is there any literature on this.

  • $\begingroup$ Would you please give a link to Lovasz theorem? $\endgroup$ Sep 23 '15 at 21:32
  • $\begingroup$ @hbm What is the outline of the "argument for the case when the graph G has a perfect matching and its girth ≥2k+1"? $\endgroup$
    – Mohemnist
    Oct 31 '15 at 6:56
  • $\begingroup$ @FedorPetrov, Here is a reference to Lovas paper: L. Lovász, On covering of graphs. In Theory of Graphs (Proc. Colloq., Tihany, 1966), 231--236. Academic Press, New York, 196 $\endgroup$
    – hbm
    Nov 20 '15 at 4:28
  • $\begingroup$ @Mohemnist check the comments below. There is an sketch of an argument. $\endgroup$
    – hbm
    Nov 20 '15 at 4:35

The question is "no" in general, as Gjergji pointed out. The question of when the answer is "yes" is difficult and only partial results are known. It is conjectured that having a 1-factor is sufficient. A recent paper that discusses the issue is this paper of Odile Favaron, François Genest and Mekkia Kouider. Here is the abstract:

Kotzig asked in 1979 what are necessary and sufficient conditions for a $d$-regular simple graph to admit a decomposition into paths of length $d$ for odd $d\gt 3$. For cubic graphs, the existence of a 1-factor is both necessary and sufficient. Even more, each 1-factor is extendable to a decomposition of the graph into paths of length 3 where the middle edges of the paths coincide with the 1-factor. We conjecture that existence of a 1-factor is indeed a sufficient condition for Kotzig’s problem. For general odd regular graphs, most 1-factors appear to be extendable and we show that for the family of simple 5-regular graphs with no cycles of length 4, all 1-factors are extendable. However, for $d\gt 3$ we found infinite families of $d$-regular simple graphs with non-extendable 1-factors. Few authors have studied the decompositions of general regular graphs. We present examples and open problems; in particular, we conjecture that in planar 5-regular graphs all 1-factors are extendable.

Finally, I should mention that I'm not a specialist in this area so my assertion that the problem is still unsolved is not gospel.

  • $\begingroup$ This is very useful! What a fun problem. Is there an example of an odd d-regular graph without a perfect matching which has a decomposition into paths of length d? $\endgroup$ May 23 '12 at 6:41
  • $\begingroup$ Yes, it is a nice problem. The graph $G_1$ in Figure 7 of that paper is an example with degree 5. Problem 3 in that paper is to do it for higher degrees. $\endgroup$ May 23 '12 at 12:18
  • $\begingroup$ If $G$ has a perfect matching $M_1$ and and of girth $\gt 2k + 2$, then $G-M_1$ is the union of $k$ $2$-factors $F_1, F_2, ..., F_k$. $(M_1 \cup F_1)$ is a simple 3-regular graph and $M_1$ is extendable into $\frac{1}{2}n$ paths of length $3$. Let $M_2$ be the matching obtained by considering each path as one edge. Similarly in $(M_2 \cup F_2)$, $M_2$ is extendable into $\frac{1}{2}n$ paths of length $3$. Since the girth $\gt 2k + 2$, at each step $F_i \cup M_i$ will be a simple cubic graph and the process could be continued until the desired paths are obtained. $\endgroup$
    – hbm
    May 24 '12 at 9:36

The answer in general is no. Already in the case $k=1$, a cubic graph is the disjoint union of paths of length $3$ if and only if it has a perfect matching. Proof: If the graph has a decomposition into paths of length $3$, take the middle edges. This will give you a perfect matching. For the other direction, suppose you have a perfect matching $M$. The complement of $M$ is a union of cycles which we can orient arbitrarily. Now to each edge in $M$ assign an outgoing and an incoming edge.

Determining which graphs admit decompositions into paths of length $k$ seems to be hard in general. In addition to the conjectures mentioned in Brendan Mckay's answer let me mention another closely related conjecture. Let's call a $k$-PPDC (perfect path double cover) a decomposition of the edges of our graphs taken with multiplicity 2, into paths of length $k$ so that each vertex appears exactly twice as an endpoint of such a path. It is conjectured that every k-regular graph admits a k-PPDC (see "Perfect path double covers of graphs" by J.A. Bondy where this conjecture is proved for k-regular graphs of girth greater than k). Notice that for $(2k+1)$-regular graphs, a path decomposition as in your problem implies a $(2k+1)$-PPDC. I don't even know the answer to this weaker conjecture for $k\geq 2$: If a $(2k+1)$-regular graph has a perfect matching, does it have a $(2k+1)$-PPDC?

  • $\begingroup$ I can't figure out this similar reasoning, could you expand? $\endgroup$
    – Will Sawin
    May 22 '12 at 19:00
  • 1
    $\begingroup$ @Will. Suppose a (2k+1)-regular graph can be written as a union of paths of length 2k+1. For each such path we orient the two 'end' edges towards each other. I claim that the oriented edges are a 2-factor. To see this, note that each vertex must have out-degree at least one, since it's degree is odd. On the other hand, the number of oriented edges is n, so each vertex has out-degree exactly 1 (and hence in-degree exactly 1). Removing the oriented edges and applying induction, we get the stronger result of a decomposition into 2-factors and one leftover 1-factor. $\endgroup$
    – Tony Huynh
    May 22 '12 at 19:32
  • $\begingroup$ Petersen showed that every regular graph of even degree can be decomposed into 2-factors, so a regular graph $G$ of odd degree $2k+1$ can be decomposed into $k$ 2-factors and one 1-factor iff that 1-factor exists. A sufficient (but not necessary) condition is that $G$ is $2k$-edge-connected. $\endgroup$ May 23 '12 at 1:03
  • $\begingroup$ @Tony: I didn't get your "and hence in-degree exactly 1" since digraphs can easily have all out-degrees 1 and a mixture of in-degrees. $\endgroup$ May 23 '12 at 1:10
  • 1
    $\begingroup$ @Tony: Here is a counterexample. Decompose $K_6$ into paths 1-2-6-3-5-4, 3-1-4-2-5-6 and 5-1-6-4-3-2. Taking the end edges oriented inwards does not make a 2-factor. The middle edges do not make a 1-factor either. $\endgroup$ May 23 '12 at 3:43

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.