Dedicated to the memory of Ivan Rival
Alexandr V. Kostochka, Vladimir Tashkinov · 2004
It is known that the edge set of a 2-edge-connected 3-regular graph can be decomposed into paths of length 3. W. Li asked whether the edge set of every 2-edge-connected graph can be decomposed into paths of length at least 3. The graphs C3, C4, C5 ,a ndK4 − e have no such decompositions. We construct an infinite sequence {Fi } ∞=0 of nondecomposable graphs. On the other hand, we prove that every other 2-edge-connected graph has a desired decomposition.