# Gallai, Tibor

## Decomposing a connected graph into paths. ★★★

Author(s): Gallai

\begin{conjecture} Every simple connected graph on $n$ vertices can be decomposed into at most $\frac{1}{2}(n+1)$ paths. \end{conjecture}

Keywords:

## Do any three longest paths in a connected graph have a vertex in common? ★★

Author(s): Gallai

\begin{conjecture} Do any three longest paths in a connected graph have a vertex in common? \end{conjecture}

Keywords: