This question is motivated by question Enumerating representations of an integer as a sum of squares . Consider a prime number $p$ congruent to $7$ modulo $8$. It can thus be written in exactly $(p+1)/2$ ways as a sum of squares of four strictly positive integers.

One way of trying to generate all solutions of $p=a^2+b^2+c^2+d^2$ with $(a,b,c,d)\in\mathbb N^4$ is to start with an arbitrary solution (obtained eg by crystal-ball gazing) $(a,b,c,d)$, to fix one of the parameters, say $a$, and to decompose $b^2+c^2+d^2$ differently as a sum of three squares, if possible.

This works seemingly always. Otherwise stated, associate to a prime $p\equiv 7\pmod 8$ a graph with $(p+1)/2$ vertices indexed by all different decompositions $p=a^2+b^2+c^2+d^2$ with $a,b,c,d\in \mathbb N$ and draw an edge between two vertices $(a,b,c,d),(a',b',c',d')$ if the intersection of $\lbrace a,b,c,d\rbrace$ and $\lbrace a',b',c',d'\rbrace$ is non-empty. Is this graph is always connected? If yes, what is typically the diameter of this graph?