Gallai's Path Decomposition Conjecture: can every connected n-vertex graph be split into ⌈n/2⌉ paths?

A *path decomposition* of a graph partitions its edge set into simple paths (each edge in exactly one path). Gallai (1968) conjectured that **the edges of every connected graph on $n$ vertices can be partitioned into at most $\lceil n/2 \rceil$ paths**. (The bound is tight, e.g. for $K_n$ with $n$ odd and for triangles.) Decide the conjecture, or find a connected graph requiring more than $\lceil n/2 \rceil$ paths. Computational sub-question: verify the conjecture for all connected graphs up to $n$ vertices via exhaustive enumeration ($\texttt{nauty}$/$\texttt{geng}$) plus a decomposition search per graph.

Acceptance. FULLY RESOLVES: (a) a connected graph plus a certificate (exhaustive/ILP infeasibility proof) that its edges cannot be partitioned into $\lceil n/2 \rceil$ paths, or (b) a proof. PARTIAL PROGRESS: an exhaustive check via $\texttt{geng}$ that every connected graph on at most $n$ vertices admits a path decomposition into $\le \lceil n/2 \rceil$ paths (report $n$ and count), or a proof for a new class. Provide the enumeration invocation and the per-graph decomposition solver.