![](/files/happy5.png)
Paths
Decomposing a connected graph into paths. ★★★
Author(s): Gallai
Conjecture Every simple connected graph on
vertices can be decomposed into at most
paths.
![$ n $](/files/tex/ec63d7020a64c039d5f6703b8fa3ab7393358b5b.png)
![$ \frac{1}{2}(n+1) $](/files/tex/e116c3c13c7f23534b92d3065799149556b9055b.png)
Keywords:
Partition of a cubic 3-connected graphs into paths of length 2. ★★
Author(s): Kelmans
Problem Does every
-connected cubic graph on
vertices admit a partition into
paths of length
?
![$ 3 $](/files/tex/4aaf85facb6534fd470edd32dbdb4e28f6218190.png)
![$ 3k $](/files/tex/7b38385e0448476b401faa5844560387ef8db56b.png)
![$ k $](/files/tex/c450c3185f7285cfa0b88d3a903c54f7df601201.png)
![$ 2 $](/files/tex/5271e36bb1c040e0f14061d89cd97d0c86d4e06f.png)
Keywords:
![Syndicate content Syndicate content](/misc/feed.png)