You can see in the graph that most nodes have at least three paths to other nodes; 7 is the only one with fewer, with only two connections, to 4 and to 6.
It's not hard to find a way to do a full walk of the graph, visiting every single node, e.g.:
1, 2, 3, 4, 9, 8, 5, 6, 7
What that translates to for Sudoku is that you could put those digits in that sequence in a single row or column and no two adjacent digits would sum to a composite number. Ah, well, drat.
Today's random thing: got myself thinking about this graph of pairs of digits 1-9 that produce prime sums. Much sparser than the complementary graph of pairs that sum to composite numbers, which I sort of knew would be true but hadn't ever examined up close.
I enjoy the resulting asymmetrical sigil, and how each distinct prime that can be summed to ends up having its own consistent slope among the diagonal connections: all 11s, all 13s, all 7s, all 5s.
@ckape So where does that leave us? We can still take that 5x5 7-cell solution and extend it with another cell on the main row and column, but we're back to a ceiling that grows by two for each step, just with a slightly smaller starting value: n = (2m - 3) instead of (2m - 2).
Question is, is there another tack we can take here, or are we stuck?