On Graver's conjecture concerning the rigidity problem of graphs (Q2276975)

By a framework in Euclidean d-space, we mean a graph whose vertices are points of \(R^ d\). A framework F in \(R^ d\) is flexible if the vertices can be moved continuously so that the distance between adjacent vertices remains unchanged while the distance between at least one pair of nonadjacent vertices is changed; if F is not flexible it is rigid. A framework F in \(R^ d\) is generic if the coordinates of the vertices of F are algebraically independent over the reals. If F is generic, then whether or not F is rigid depends entirely on the graph theoretical properties of F and not a particular generic embedding. Of particular interest are the edge minimal generically rigid graphs for dimension d or the d-isostatic graphs. If one attaches a new vertex of valice d to a d- isostatic graph, one gets a larger d-isostatic graph. Similarly, if one deletes an edge x from a d-isostatic graph and attaches a new vertex of valence \(d+1\) to x, y and any other d-1 vertices, one gets a larger d- isostatic graph. It is well-known that all 2-isostatic graphs can be constructed from a single edge by a sequence of the above two steps; it is also known that these two steps do not suffice in higher dimensions. The natural next construction to consider is the deletion of two edges, xy and zw and the attachment of a new vertex of valence \(d+2\) to x, y, z, w and any other d-2 vertices. The construction results in a larger d- isostatic graph in dimensions one and two; it is not known if this construction works for dimension three. The author proves that the construction does not always yield a d-isostatic graph when d is four.