Igor Pak suggested I ask this as a separate question. In [Extensions of the Koebe–Andreev–Thurston theorem to sphere packing?](https://mathoverflow.net/questions/85547/extensions-of-the-koebeandreevthurston-theorem-to-sphere-packing) it was asked whether there were simple conditions to decide whether a finite graph could be expressed by a bunch of spheres in $\mathbb R^3,$ two spheres touching if and only if the relevant vertices shared an edge. 


Scott Carnahan and I are of the opinion that any graph on $n$ vertices can be placed in $\mathbb R^{n-1}$ in the manner described. It is proved in Igor's book that the complete graph can be placed in $\mathbb R^{n-2}$ and no smaller dimension, one regular simplex with unit radii and then one extra sphere in the center. Of course, the complete graph can also be placed as a regular simplex with all unit spheres in $\mathbb R^{n-1}.$ But the varying radius question seems more fortunate, we get the same answer, if it works, in $\mathbb H^{n-1}$ and $\mathbb S^{n-1}.$


So, that is the initial question, can anyone prove that any graph on $n$ vertices, however many or few edges, can be placed in $\mathbb R^{n-1}$ as a set of spheres, if we allow varying radius? 


Secondarily, and I have not the slightest idea, is there any sort of expected value of the minimum dimension, or, at least, some sort of "normal behavior" for this, meaning that "most" graphs on $n$ vertices need a minimum dimension of about \_\_\_\_? 



Minimum dimension for sphere packing a graph in Euclidean space
Start with a regular simplex with unit length edges in ${\mathbf{R}}^{n-1}$, representing $K\_n$. In any non-degenerate simplex, one can increase or decrease the length of any edge by a sufficiently small amount, leaving all other edge lengths fixed and flexing the dihedral angle opposite to the edge. Do this to increase the length of every edge in $K\_n$ that is not present in your given graph $G$, one edge at a time. Finally, place radius-1/2 balls at the vertices of the resulting simplex. The result is a sphere packing representing $G$.


