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:

Syndicate content