Decomposing a connected graph into paths.

Definitions and mathematical statement

Shared notation.

$\mathbb N=\{1,2,\ldots\}$, and $\mathbb Z,\mathbb Q,\mathbb R,\mathbb C$ denote the integers, rationals, reals and complex numbers. Any other conventions are specified locally.

For a finite simple graph $G$, a path is a sequence of distinct vertices with edges between consecutive vertices. A path decomposition is a partition of $E(G)$ into edge sets of paths; vertices may occur in different paths. Write $n=|V(G)|$.

Statement recorded in the supplied source.

Does every connected graph $G$ admit a path decomposition with at most \[\left\lfloor\frac{n+1}{2}\right\rfloor=\left\lceil\frac n2\right\rceil\] paths? [S2]

Short English statement

Can the edges of every connected graph be partitioned into at most half its order rounded up paths?

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, UnsolvedMath: A Curated Collection of Open Mathematics Problems, record 3188 (OPG-46583). CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Open Problem Garden, Decomposing a connected graph into paths., original node 46583, statement and mathematical discussion. https://www.openproblemgarden.org/op/decomposing_a_connected_graph_into_paths.