A property of  primes  congruent to $7\pmod 8$ expressed as sums of four squares. 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?
 A: Too long for a comment. Your problem reminds me of this. If anything directly helpful comes to mind on your problem I will let you know of course.
Please allow me to draw your attention to the fascinating Markov-Hurwitz Diophantine equation
$$ x_1^2 + x_2^2 + \cdots + x_n^2 = a \; x_1 x_2 \ldots x_n $$
in positive integers, with
$$ 1 \leq a \leq n $$
as shown by Hurwitz (1907). 
See my answer to
Numbers characterized by extremal properties
especially the Markov tree, Markov (1880)
http://en.wikipedia.org/wiki/Markov_number
If, for example, $x_1$ is fairly large , it can be replaced
by $ a x_2 x_3 \ldots x_n - x_1 $ to give another solution with smaller values. This process can be repeated until one arrives at a "fundamental solution" which satisfies a certain inequality: ordered so that $x_1$ is indeed the largest, a fundamental solution has 
$$ 2 x_1 \leq a x_2 x_3 \ldots x_n .$$
So a fundamental solution is the root of a tree of solutions for fixed pair $(n,a).$ The first time that a pair $(n,a)$ requires a disconnected forest is $(n=14, a=1)$ one tree with (decreasingly ordered) root
$(6,4,3,1,1,\ldots)$ and another tree with ordered root $(3,3,2,2,1,1,\ldots).$ 
So many things...my conjecture that, for a fundamental solution in nonincreasing order, 
$ 5 x_1^2 \leq 9 ( n+6) .$ Finally the right hand side $ a \; x_1 x_2 \ldots x_n $ can be replaced by any of those symmetric polynomials where all exponents are at most one, as we still get  trees.
A: I won't get into the question of graph connectedness but (assuming it is connected!) I may be able to offer some intuition on the graph diameter problem.  You could employ probabilistic methods to get a good bound.  You already know the number of vertices (p+1)/2.  You need to compute the probability of edge connectivity.
If $R_3(n)$ is the number of ways 'n' can be represented as the sum of 3 squares, then the degree of any vertex, after iterating through all four coefficients, should be $ 
[sum_{i=1}^
  {4}(R_3(p- coeff_i) - 1)
] 
$. 
The number of total edges in the graph is upper bounded by
$ 
[sum_{i=1}^
  {\sqrt{p}} (R_3(i)(R_3(i) - 1))/2
] 
$    
I can't visualize the distribution of this sum-of-squares graph but you could adapt the methods which were applied in http://www1.cs.columbia.edu/~coms6998/Notes/lecture3.pdf 
See also 


*

*Fan Chung's summary on graph diameter http://math.ucsd.edu/~fan/research/diad.pdf

*Béla Bollobás. The Diameter of Random Graphs. Transactions of the American Mathematical Society, Vol. 267, No. 1 (Sep., 1981), pp. 41-52
Published by: American Mathematical Society
Stable URL: http://www.jstor.org/stable/1998567

*Edgar Palmer's book Graphical Evolution
