You are an expert at summarizing long articles. Proceed to summarize the following text: 
an interesting and difficult problem in graph theory is the graph embedding problem . the problem is as follows : given a collection of vertices in @xmath1 and the pairwise distances between some of them , find the positions of the vertices up to some arbitrary rigid motion . the problem has shown to be np - hard @xcite ; however , solutions may be found using semidefinite programming @xcite . unfortunately the embeddings given by semidefinite programming may be in some larger dimensional space rather than @xmath0-dimensional . however , if the framework is _ universally rigid _ then solutions are automatically constrained to be @xmath0-dimensional . this paper seeks to address the question raised by gortler and thurston : `` for a graph @xmath4 which is @xmath0-ggr is there always a generic framework in the space of @xmath0-dimensional frameworks , @xmath5 that is universally rigid?''@xcite . this question is answered in the affirmative for @xmath6 and @xmath7 , and for an infinite number of @xmath0-ggr graphs when @xmath8 . the key tool to obtain this result is the hennenberg operation . the hennenberg operation is a vertex and edge addition to a graph , which preserves important rigidity properties . connelly proved that hennenberg operations preserve global rigidity @xcite . this paper expands that result by proving that hennenberg operations preserve universal rigidity for suitable frameworks . hennenberg operations and edge additions can be used to build @xmath0-ggr graphs from the complete graph @xmath9 . all graphs built in this manner will possess a generic @xmath0-dimensional universally rigid ( @xmath0-gur ) framework . every non - trivial 1 and 2-ggr graph is the result of hennenberg operations and edge additions to @xmath9 , allowing us to conclude the main result . all 1 and 2-ggr graphs and an infinite number of @xmath0-ggr graphs for @xmath8 have a @xmath0-gur framework . the complete answer to gortler and thurston s question is still unknown in higher dimensions but we offer the following conjecture . all d - ggr graphs have a d - gur framework . thanks to kiril ratmanski and andrew fanoe for their helpful comments and ideas . thanks to timothy sun for showing that 1-ggr graphs can be characterized by the whitney synthesis theorem . special thanks to dylan thurston for his enormous help throughout the entire process . * graphs and frameworks : * a _ graph _ @xmath4 is a set @xmath10 of @xmath11 vertices , and a set @xmath12 of @xmath13 edges containing some collection of 2 member subsets of @xmath10 . a _ framework _ @xmath14 , is an embedding of the vertices and edges in @xmath1 @xmath15 where each @xmath16 is the coordinate of a vertex in @xmath1 . let @xmath5 denote the set of all frameworks of @xmath4 in dimension @xmath0 . a framework is _ generic _ if the coordinates of its vertices do not satisfy any nontrivial polynomial with rational coefficients . * local rigidity : * two different embeddings @xmath14 , and @xmath17 of a graph @xmath4 are said to be _ equivalent _ written @xmath14@xmath18@xmath17 if @xmath19 for all @xmath20 edges in @xmath12 . a framework is said to be _ locally flexible _ if there exists a non - constant analytic path @xmath21\to { \mathbb{r}}^{vd}$ ] such that @xmath22 and @xmath23 $ ] and @xmath24 can not be extended to a euclidean motion of @xmath1 . if a framework is not locally flexible then it is _ locally rigid_.    * infinitesimal rigidity : * the _ half edge length squared function _ @xmath25 , where @xmath26 @xmath27 is a map from frameworks to the space of edge lengths . if two frameworks are equivalent @xmath28 then by definition @xmath29 . the jacobian @xmath30 of the edge - length squared function is called the _ rigidity matrix _ , and gives a simple way to determine local rigidity for generic frameworks . the matrix is a @xmath31 matrix where each row represents an edge and each column represents the one of the @xmath0 coordinates of a vertex . the rigidity matrix has an important connection to local rigidity , as the first derivatives of paths preserving edge lengths are in the kernel of the matrix . thus every euclidean motion is in the kernel , and as long as the framework does not lie in some lower dimensional affine subspace of @xmath1 , the dimension of the kernel is at least @xmath32 . a framework is _ infinitesimally rigid _ if the kernel of the rigidity matrix is minimal , or equivalently @xmath33 . if a framework is infinitesimally rigid then it is locally rigid . if a generic framework of a graph with d+1 or more vertices is locally rigid in @xmath1 , then it is infinitesimally rigid . furthermore if there exists a single infinitesimally rigid framework , then every generic framework is infinitesimally rigid . * stresses : * an _ equilibrium stress _ on a framework is an assignment of a real number @xmath34 to each edge of a framework satisfying @xmath35 . the _ stress vector _ @xmath36 is a @xmath37 vector consisting of the ordered stresses on each edge . it is not difficult to see that @xmath36 is in the kernel of the transpose of the rigidity matrix , and in fact the space of all stresses is precisely this kernel . equilibrium stress matrix _ @xmath38 is a @xmath39 matrix satisfying : \(1 ) @xmath40    \(2 ) @xmath41 if @xmath42 and @xmath43    \(3 ) @xmath44 if @xmath42 and @xmath45    \(4 ) @xmath46 is chosen so the row sum is zero . the entries of the stress matrix are uniquely determined by @xmath36 so this paper will freely interchange between equilibrium stresses and stress matrices . since the row sum of the matrix is zero the vector of all ones @xmath47 is always in the kernel of the stress matrix . additionally the @xmath0 coordinate projections of the vertices lie in the kernel of the stress matrix . this condition is easy to check since @xmath35 must be satisfied . a generic framework with @xmath48 or more vertices can not lie in a lower dimensional affine subspace , so the @xmath0 coordinate projections are linearly independent . thus for a generic framework with @xmath48 or more vertices , the nullity of the stress matrix is at least @xmath48 . * redundant rigidity : * an edge in a locally rigid framework is _ redundant _ if removal of said edge preserves local rigidity . a framework is _ redundantly rigid _ if every edge of the framework is redundant . a framework is redundantly rigid if and only if there exists a stress which is nonzero on every edge . * global rigidity : * two frameworks @xmath14 and @xmath17 are _ congruent _ written @xmath49 if @xmath19 for all @xmath50 . a @xmath0-dimensional framework @xmath14 is _ globally rigid in dimension _ @xmath0 if every framework in @xmath5 equivalent to @xmath14 is also congruent to @xmath14 .    a graph is generically globally rigid in dimension @xmath0 ( @xmath0-ggr ) if and only if it has a generic framework with a stress matrix of minimal nullity d+1 , or it is the complete graph on d+1 or fewer vertices . connelly showed that the stress condition was sufficient , and gortler , healy , and thurston showed that it was necessary , implying that global rigidity is a generic property . since global rigidity is a generic property , it can be thought of as a property of a graph , and such graphs are called _ generically globally rigid in dimension _ @xmath0 ( @xmath0-ggr ) . the stress condition is not particularly intuitive , and other attempts have been made to characterize global rigidity combinatorially . * vertex connectivity : * a graph is @xmath51__-vertex - connected _ _ if the deletion of any @xmath52 vertices leaves a connected graph . if a graph is @xmath0-ggr then it is redundantly rigid and d+1-vertex - connected .    in the same paper hendrickson conjectured that these conditions would also be sufficient . in @xmath6 2-vertex - connectedness subsumes redundant rigidity , and it is easy to see that all 2-vertex - connected graphs are 1-ggr . in @xmath7 , connelly and jackson and jordn proved that these conditions are sufficient for global rigidity ( see theorem 5.7 ) @xcite , @xcite . unfortunately , in @xmath53 and above connelly showed that there are graphs which satisfy hendrickson s conditions , but fail to be globally rigid . in fact there is not even a combinatorial characterization of local rigidity in dimensions 3 or higher @xcite . the lack of a general combinatorial characterization of @xmath0-ggr graphs for @xmath8 makes conjecture 1.2 difficult to resolve . * universal rigidity : * a @xmath0-dimensional framework , @xmath14 is _ universally rigid _ if every framework in @xmath54 equivalent to @xmath14 is also congruent to @xmath14 where @xmath55 . if the framework is also generic then it is a _ @xmath0-dimensional generic universally rigid framework _ ( @xmath0-gur framework ) . unlike global rigidity , universal rigidity is not a generic property . a graph @xmath4 is _ @xmath0-semi - universally rigid _ ( @xmath0-sur ) if it has a @xmath0-gur framework , but has other generic frameworks which fail to be universally rigid in @xmath0-dimensions . figure 1 has a very simple example of a graph with this behavior . in section 6 we construct a non - trivial family of @xmath0-sur graphs . certain classes of graphs , like complete graphs , are generically universally rigid . any framework of a complete graph is universally rigid .    for frameworks of complete graphs equivalence and congruence are the same condition . if a framework is @xmath0-gur then it is a framework of a @xmath0-ggr graph . if a framework is universally rigid then it must be globally rigid in dimension  @xmath0 . since the framework is generic all other generic @xmath0-dimensional frameworks are globally rigid so the graph is @xmath0-ggr . * hennenberg operations : * a @xmath0-hennenberg operation is an edge and vertex addition to a graph that preserves important rigidity properties . a @xmath0-hennenberg operation is performed on a graph by deleting an edge @xmath56 , adding a new vertex @xmath57 and edges @xmath58 and @xmath59 , and adding an additional @xmath60 edges to @xmath57 which are connected to any @xmath60 distinct vertices that are not @xmath61 or @xmath62 . it is important to note that @xmath0-hennenberg operations may only be performed on graphs with at least @xmath48 vertices , since the operation requires @xmath48 distinct vertices . connelly showed that @xmath0-hennenberg operations on a @xmath0-ggr graph resulted in another @xmath0-ggr graph @xcite . this paper extends that result to show that a @xmath0-hennenberg operation takes a graph with a @xmath0-gur framework to another graph with a @xmath0-gur framework . if a generic d - dimensional framework with d+2 or more vertices is universally rigid then it has a positive semi - definite ( psd ) stress matrix of nullity d+1 . alfakih proved the theorem for a matrix of any rank @xcite , @xcite . gortler and thurston strengthened the theorem by showing the stress matrix has minimal nullity . * conics at infinity : * let @xmath63 be a symmetric @xmath64 non - zero matrix . a conic at infinity @xmath65 is the set of points @xmath66 : @xmath67 . the edge directions of a framework @xmath14 lie on a conic at infinity if there exists a non - zero symmetric matrix @xmath63 satisfying @xmath68 for all @xmath45 . a d - dimensional framework with at least d+2 vertices is universally rigid if it has a psd stress matrix of nullity d+1 and its edge directions do not lie on a conic at infinity . connelly proved this result across a number of papers @xcite and @xcite , however due to the centrality of the result to this paper a condensed and slightly modified proof is presented below . let @xmath69 be the energy function @xmath70 . @xmath71 where @xmath72 is the stress given by the fixed stress vector @xmath73 for the framework @xmath74 . let @xmath75 be the @xmath76 vector of the @xmath77 coordinate entry of each of the @xmath11 vertices of @xmath14 , then an equivalent version of @xmath69 is given by @xmath78 where again @xmath79 is the fixed stress matrix determined by @xmath73 . now let @xmath14 be a framework in dimension @xmath0 with a psd stress matrix @xmath80 , and whose edges do not lie on a conic at infinity . let @xmath17 be some framework in dimension @xmath55 , with @xmath14@xmath18@xmath17 . now consider @xmath81 , where @xmath82 is the stress vector determined by @xmath80 . since the coordinate projections of @xmath14 are in the kernel of @xmath80 , by equation ( 2 ) @xmath83 . by equation ( 1 ) @xmath81 is a function on the edge lengths . thus if @xmath14@xmath18@xmath17 then @xmath84 . @xmath80 is a psd matrix , so @xmath85 such that @xmath86 . thus , @xmath87 @xmath88 the kernel of @xmath80 consists of the coordinate projections @xmath75 and the vector of all ones @xmath47 , thus each coordinant projection @xmath89 must be some linear combination of these vectors . therefore @xmath90 is obtained from @xmath91 by some affine transformation of @xmath1 to @xmath92 . in other words @xmath93 for some fixed @xmath94 matrix @xmath95 and a fixed @xmath96 vector @xmath97 for all verticies @xmath98 . the transformation must preserve edge lengths so @xmath99 @xmath100 @xmath101 is clearly a symmetric matrix ; thus either it is the zero matrix or the edge directions lie on a conic at infinity . since the edge directions do not lie on a conic at infinity by hypothesis , @xmath102 let @xmath103,@xmath104 be vertices not necessarily sharing an edge . then @xmath105 thus every framework @xmath17 in dimension @xmath2 equivalent to @xmath14 is also congruent to @xmath14 as desired . let g(p ) be a generic d - dimensional framework of a finite graph g where each vertex has degree at least d. then the edge directions of g(p ) do not lie on a conic at infinity . a generic d - dimensional framework with d+2 or more vertices is universally rigid if and only if it has a psd stress matrix of nullity d+1 . theorem 3.1 already establishes one direction . to prove the other direction note the nullity of the stress matrix is @xmath48 , therefore the framework is globally rigid and thus @xmath106-connected . since the graph is @xmath106-connected the degree of each vertex must be at least @xmath0 . by proposition 3.3 , the edge directions of the framework do not lie on a conic at infinity . the framework then satisfies the hypothesis of theorem 3.2 . in this section we derive a few simple results about stress matrices that we will need for our main argument . the first four results deal with perturbations of eigenvalues and the last two results relate to kernels . * normal matrices : * a real valued @xmath107 matrix @xmath95 is _ normal _ if @xmath108 . it is easy to see that any symmetric matrix @xmath109 is normal since @xmath110 . let a , f be @xmath107 matrices , with a , a+f normal . let @xmath111 be the eigenvalues of a in some order and @xmath112 be the eigenvalues of a+f in some order . then there exists a permutation @xmath113 of the integers @xmath114 such that @xmath115^{1/2 } \ ! \ ! \ ! \leq \lvert f\rvert_{2}\ ] ]    let a and c be @xmath107 symmetric matrices . let b be the @xmath107 matrix such that @xmath116 . let @xmath117 be the smallest absolute value of an eigenvalue of a. if @xmath118 then c has at least as many positive and negative eigenvalues as a.    @xmath95 and @xmath119 are symmetric , so they are normal and all their eigenvalues are real . let @xmath111 be the eigenvalues of @xmath95 , and @xmath112 be the eigenvalues of @xmath119 . by the hoffman and wielandt theorem , @xmath120 @xmath121 thus @xmath122 . since @xmath123 if @xmath124 then @xmath125 and if @xmath126 then @xmath127 . thus @xmath119 has at least as many positive and negative eigenvalues as @xmath95 . let a be a @xmath39 stress matrix of nullity @xmath48 for some d - dimensional framework g(p ) . let c be a @xmath39 stress matrix for some d - dimensional framework h(q ) , not necessarily different from g(p ) . let b be the matrix such that @xmath116 . let @xmath117 be the smallest absolute value of an eigenvalue of a. if @xmath118 then a and c have the same number of positive and negative eigenvalues . @xmath95 and @xmath119 satisfy corollary 4.1 so @xmath119 has at least as many positive and negative eigenvalues as @xmath95 . thus @xmath119 has nullity at most @xmath48 . but @xmath48 is the minimal nullity for stress matrices so the rest of the of the eigenvalues of @xmath119 must be zero . therefore @xmath95 and @xmath119 have the same number of positive and negative eigenvalues . let a , b be @xmath39 stress matrices for some d - dimensional framework g(p ) , where a is of nullity d+1 . then @xmath128 such that @xmath95 and @xmath129 have the same number of positive and negative eigenvalues , and @xmath129 is a stress matrix for g(p ) . it is easy to check that if @xmath95 and @xmath130 are stress matrices for a framework then @xmath131 is also a stress matrix for the same framework . let @xmath132 , and let @xmath133 be the smallest absolute value of an eigenvalue of @xmath95 . pick @xmath134 and apply corollary 4.2 . now we turn to analyzing kernels of matrices . first we define a way to measure distances between linear subspaces . * hausdorff distance : * let ( @xmath135 , @xmath136 ) be a metric space and let @xmath95 , @xmath130 be subsets of @xmath135 . the hausdorff distance between @xmath95 and @xmath130 , written @xmath137 is defined as @xmath138 the distance between linear subspaces @xmath139 and @xmath140 of @xmath1 is defined as the hausdorff distance between @xmath141 and @xmath142 , where @xmath143 is the unit sphere in @xmath144 . @xmath143 is a bounded set so the distance will be well defined . suppose that @xmath145 is a matrix whose entries are integral polynomial functions of the real variables @xmath146 . let @xmath147 be the maximum rank of @xmath148 and suppose that @xmath149 . then @xmath150 such that for @xmath151 the hausdorff distance between the linear subspaces @xmath152 and @xmath153 is less than @xmath154 . if a , b are psd matrices then @xmath155 . let @xmath156 , @xmath157 be matrices such that @xmath158 and @xmath159 . let @xmath160 . @xmath161 therefore , @xmath162 and @xmath163 , which holds if and only if @xmath164 and @xmath165 . thus @xmath160 if and only if @xmath166 and @xmath167 . it follows that @xmath168 . let h be obtained from g by a single edge addition . if g has a d - gur framework then h has a d - gur framework . let @xmath14 be the @xmath0-gur framework of @xmath4 . by theorem 3.1 @xmath14 has a psd stress matrix @xmath95 of nullity @xmath48 . let @xmath169 be a @xmath0-dimensional framework of @xmath170 with the same vertex positions as @xmath14 . @xmath14 was generic so @xmath169 is also generic . define the stress on the new added edge to be @xmath171 then @xmath95 is a stress matrix for @xmath169 as well . thus @xmath169 is a generic @xmath0-dimensional framework with a psd stress matrix of nullity @xmath48 . therefore @xmath170 has a @xmath0-gur framework . this proof is so trivial since adding an edge can not do anything but make a rigid framework more rigid . let g be a graph with @xmath172 or more vertices . let h be obtained from g by a single @xmath0-hennenberg operation . if g has a d - gur framework then h has a d - gur framework . let @xmath14 be the @xmath0-gur framework of @xmath4 . by theorem 3.1 @xmath14 has a stress matrix @xmath95 which is psd and of nullity @xmath48 . @xmath14 must also be globally rigid , so by theorem 2.4 it is redundantly rigid . @xmath14 is redundantly rigid , therefore it has a stress matrix @xmath130 for which the stress on every edge is non - zero . pick @xmath173 so that every non - zero entry of @xmath95 is still non - zero in @xmath174 . by corollary 4.3 , pick @xmath175 so that @xmath176 is still psd and nullity @xmath48 . pick @xmath177 and let @xmath178 . @xmath80 is now an equilibrium stress matrix for @xmath14 which is psd of nullity @xmath48 and defines a non - zero stress @xmath179 on every edge . arrange @xmath80 so that the two vertices whose edge was eliminated by the @xmath0-hennenberg operation , say @xmath61 and @xmath62 , correspond to the last two columns and rows of the matrix respectively . let @xmath180 be a @xmath0-dimensional framework of @xmath170 , where @xmath181 for all @xmath182 and the extra vertex , @xmath183 , of @xmath170 is placed somewhere along the line going through the eliminated edge @xmath56 . note that the configuration of @xmath180 is almost the same as the configuration of @xmath14 , and that @xmath180 is not a generic framework ( see figure 2 ) . let @xmath184 be the directed length of the old edge , let @xmath185 be the directed length of edge @xmath58 , and let @xmath186 be the directed length of edge @xmath187 where we require @xmath188 . note choosing a value for @xmath189 or @xmath190 determines the placement of the final vertex @xmath57 . we define a stress vector @xmath191 on @xmath180 as follows :    \(1 ) @xmath192 if @xmath20 is an edge of @xmath4 and @xmath170 ,    \(2 ) @xmath193 ,    \(3 ) @xmath194 , and    \(4 ) @xmath195 if @xmath196 . these conditions constitute an equilibrium stress on @xmath180 . let @xmath197 be the @xmath198 stress matrix defined by this stress . arrange @xmath197 so that the first @xmath11 rows and columns correspond to the same vertices as in @xmath80 , and the last row and column correspond to the new vertex @xmath57 . let @xmath199 be a @xmath200 matrix , where the top left @xmath39 block has the same entries as @xmath80 and the rest of the entries are zero . @xmath80 is psd of nullity @xmath48 , so @xmath199 is psd of nullity @xmath172 . the last column and row of @xmath199 , which contains all zeros , corresponds to the vertex @xmath57 . since the stress on each edge except for @xmath56 , @xmath58 , and @xmath187 is the same , @xmath199 and @xmath197 have the same entries except for a @xmath201 block in the bottom right corner . let @xmath156 be the @xmath200 matrix such that @xmath202 . let @xmath203 be the non - zero @xmath201 block of @xmath156 . then @xmath204 since @xmath188 it follows that @xmath205 . if @xmath206 , pick @xmath207 . then the diagonal entries of @xmath156 are positive , so @xmath156 is psd . if @xmath208 , pick @xmath209 . then the diagonal entries of @xmath156 are positive , so @xmath156 is psd . the sum of two psd matrices is psd so @xmath197 is psd . using lemma 4.5 , @xmath210 . because @xmath211 , the standard basis vector @xmath212 is not in the kernel of @xmath156 but is clearly in the kernel of @xmath199 . thus , the dimension of the kernel of @xmath197 is strictly less than the dimension of the kernel of @xmath199 , so @xmath213 . therefore , @xmath197 is psd and of nullity @xmath48 . all that is left is to perturb @xmath180 to a generic configuration . to be able to do this @xmath180 must be infinitesimally rigid , and the following proposition proves that it is . suppose g(p ) is a framework in @xmath1 and h is obtained from g by a hennenberg operation . if h(q ) is a framework such that the @xmath60 additional edges and the subdivided edge of g do not lie in a @xmath60 affine subspace , then h(q ) is infinitesimally rigid .    in order for the @xmath60 additional edges and the subdivided edge to lie in a @xmath214-dimensional affine subspace @xmath61 , @xmath62 , @xmath57 and the @xmath60 vertices connected to @xmath57 must all lie in a @xmath214-dimensional affine subspace this means that for @xmath14 the vertices @xmath61 , @xmath62 and @xmath60 other vertices all lie in a @xmath214-dimensional affine subspace . however such a configuration is not generic , contradicting our hypothesis on @xmath14 , so @xmath180 is infinitesimally rigid .    by theorem 2.1 , we now know that every generic framework of @xmath170 in dimension @xmath0 will be infinitesimally rigid , so the kernel of the transpose rigidity matrix for all of these frameworks will be minimal . non - generic points are measure zero in @xmath215 so @xmath216 there exists a generic framework , @xmath217 such that @xmath218 . the entries of the rigidity matrix are polynomial functions of the vertex positions , so by lemma 4.4 @xmath219 @xmath220 such that the distance between @xmath221 and @xmath222 is less than @xmath154 . let @xmath223 , then @xmath224 . therefore @xmath225 such that @xmath226 . define a stress @xmath227 on @xmath217 such that @xmath228 and let @xmath229 be the stress matrix defined by this stress vector . the stress on each edge of @xmath217 differs from the stress on @xmath180 by at most @xmath230 . let @xmath231 be the matrix satisfying @xmath232 . the norm of the matrix @xmath233 for some constant @xmath234 . finally , pick @xmath235 so that @xmath154 is so small that f satisfies the hypothesis of corollary 4.2 . then @xmath229 is a psd stress matrix of nullity @xmath48 . by corollary 3.4 , @xmath217 is a @xmath0-gur framework . this completes the proof of the theorem . let g be a graph with @xmath172 or more vertices . let h be obtained from g by any sequence of edge additions and @xmath0-hennenberg operations . if g has a @xmath0-gur framework then h does as well . for any d an infinite number of @xmath0-ggr graphs have a @xmath0-gur framework . any graph built from @xmath0-hennenberg operations and edge additions to the complete graph @xmath9 will have a @xmath0-gur framework by corollary 5.4 and proposition 2.5 . * path , path addition , and whitney synthesis : * let @xmath4 be a graph . a _ path _ in @xmath4 is a sequence of vertices of @xmath4 such that each vertex in the sequence is connected to the next vertex in the sequence by an edge . path addition _ to a graph @xmath4 is the addition to @xmath4 of a path between two existing vertices of @xmath4 , such that the edges and internal vertices of the path are not in @xmath4 . a _ whitney synthesis _ of a graph @xmath170 from a graph @xmath4 is a sequence of graphs @xmath236 where @xmath237 and @xmath238 , and @xmath239 is the result of a path addition to @xmath240 . a graph g is 2-vertex connected if and only if g is a cycle or a whitney synthesis from a cycle . every 1-ggr graph with 3 or more vertices can be built from a sequence of hennenberg operations and edge additions to @xmath241 .    by theorem 2.4 every @xmath0-ggr graph with @xmath172 or more vertices must be @xmath48-vertex connected and redundantly rigid . for a 1-dimensional framework , redundant rigidity is equivalent to the graph being 2-edge - connected . 2-edge - connectedness is a weaker condition than 2-vertex - connectedness , so only 2-vertex - connectivity needs to be considered . by the whitney synthesis theorem every 2-vertex - connected graph is either a cycle or a path addition to a cycle . a 1-hennenberg operation on a graph subdivides an edge by adding a vertex . a cycle with @xmath11 vertices can easily be generated from @xmath241 by performing @xmath242 hennenberg operations on the graph . a path addition is simply an edge addition to a graph , followed by any number of hennenberg operations on the added edge . any sequence of path additions can be formed by successive edge additions and hennenberg operations . if a graph @xmath4 with at least 4 vertices is redundantly rigid in @xmath243 and 3-vertex connected then @xmath4 can be obtained from @xmath244 by a sequence of hennenberg operations and edge additions . redundant rigidity and 3-vertex connectivity are necessary and sufficient conditions for global rigidity in 2-dimensions , thus every 2-ggr graph on 4 or more vertices can be built from hennenburg operations and edge additions on @xmath244    every ggr graph in 1 and 2-dimensions has a universally rigid generic framework . suppose @xmath4 is a 2-ggr graph ( 1-ggr graph ) . if @xmath4 has 4 ( 3 ) or more vertices then @xmath4 satisfies theorem 5.7 ( proposition 5.6 ) . thus corollary 5.4 applies to @xmath4 , so @xmath4 has a 2-gur framework ( 1-gur framework ) . if @xmath4 has 3 ( 2 ) or fewer vertices than @xmath4 is a complete graph , and therefore universally rigid this completes the proof of theorem 1.1 . we now turn to the construction of an infinite family of @xmath0-sur graphs . recall that given some framework @xmath14 the space of stresses on @xmath14 is the kernel of the transpose rigidity matrix @xmath245 . let @xmath236 be a sequence of graphs where @xmath246 is the result of a @xmath0-hennenberg operation on @xmath247 and @xmath248 has a @xmath0-gur framework . if @xmath249 and @xmath250 are generic frameworks then @xmath251 .    by theorem 5.2 and proposition 2.6 , each @xmath246 is @xmath0-ggr . therefore the generic frameworks of each @xmath246 are infinitesimally rigid so the rank of the rigidity matrix @xmath30 is maximal . let @xmath252 and @xmath253 denote the number of vertices and edges of @xmath246 respectively . for a generic framework @xmath250 @xmath254 . let @xmath255 where @xmath250 is generic . then @xmath256 . now we proceed by induction . the base case is trivial as @xmath257 . now suppose that @xmath258 . then @xmath259 thus @xmath260 . let @xmath236 be a sequence of graphs where @xmath246 is the result of a @xmath0-hennenberg operation on @xmath247 and @xmath261 the complete graph on @xmath172 vertices . if @xmath250 is generic then @xmath262 . in particular @xmath250 has a one dimensional space of stresses . @xmath261 the complete graph on @xmath172 vertices thus @xmath263 . let @xmath249 be a generic framework . @xmath248 is @xmath0-ggr so @xmath249 is infinitesimally rigid . therefore @xmath264 by proposition 6.1 @xmath262      each @xmath246 has a @xmath0-gur framework . thus we only need to show that for @xmath266 the graph @xmath246 has a generic @xmath0-dimensional framework which is not universally rigid . for some @xmath267 let @xmath268 be a @xmath0-gur framework of @xmath269 . by corollary @xmath268 has a @xmath270 stress matrix @xmath271 which is unique up to scaling . @xmath268 is @xmath0-gur so @xmath271 is psd of nullity @xmath48 . @xmath268 is also redundantly rigid so @xmath271 must also define a stress that is non - zero on every edge . let @xmath272 and set @xmath273 . we now proceed as in theorem 5.2 and we obtain @xmath274 stress matrices @xmath275 and @xmath276 . the upper left @xmath277 block of @xmath275 has the same entries as @xmath271 and the entries of @xmath278 row and column of @xmath275 are all zero . @xmath276 and @xmath275 have the same entries except for a @xmath201 block in the bottom right corner . @xmath156 is the @xmath274 matrix such that @xmath279 . let @xmath203 be the non - zero @xmath201 block of @xmath156 . recall that @xmath204    since @xmath188 it is not difficult to see that @xmath205 . if @xmath208 pick @xmath207 . then the diagonal entries of @xmath156 are negative so @xmath156 is nsd . if @xmath206 pick @xmath280 @xmath281 . then the diagonal entries of @xmath156 are negative so @xmath156 is nsd . let @xmath282 be the last standard basis vector . @xmath283 thus @xmath276 can not be psd . however , @xmath284 is a psd @xmath274 matrix of nullity @xmath172 so @xmath285 thus it follows that @xmath286 . the standard basis vector @xmath287 but @xmath288 so the two kernels are not identical . the dimension of the kernel of @xmath156 is greater than or equal to the dimension of the kernel of @xmath284 . therefore @xmath289 . so @xmath290 such that @xmath291 . @xmath292 thus @xmath276 can not be nsd . therefore @xmath276 is indefinite . again we proceed as in theorem 5.2 and we obtain a generic framework @xmath235 such that @xmath293 and @xmath294 . we then pick @xmath154 small enough that f satisfies the hypothesis of corollary 4.1 . then @xmath295 has at least as many positive and negative eigenvalues as @xmath276 . since @xmath276 is indefinite @xmath295 must also be indefinite . by corollary 6.2 @xmath295 is a unique stress matrix for @xmath296 up to scale . therefore the stress matrices of @xmath296 are either indefinite or are the zero matrix . the zero matrix has nullity greater than @xmath48 so @xmath296 has no psd stress matrix of nullity @xmath48 . finally by corollary 3.4 @xmath296 can not be universally rigid . so @xmath297 is a @xmath0-sur graph .
a @xmath0-dimensional framework is an embedding of the vertices and edges of a graph in @xmath1 . 
 a @xmath0-dimensional framework is globally rigid if every other @xmath0-dimensional framework with the same edge lengths has the same pairwise distances between the vertices . 
 a graph is generically globally rigid in dimension @xmath0 ( @xmath0-ggr ) if every generic framework is globally rigid . 
 the @xmath0-dimensional framework of a @xmath0-ggr graph is universally rigid if for @xmath2 every @xmath3-dimensional framework with the same edge lengths has the same pairwise distances between the vertices . 
 we establish a strong connection between global and universal rigidity by showing that all 1 and 2-ggr graphs and an infinite number of higher dimensional @xmath0-ggr graphs have a generic universally rigid framework . 
 = 1