
Question 2 can be addressed computationally by computing the ranks of generic rigidity matrices corresponding to the sequence of graphs.
I'll show below that the 6th 2extension for one choice of sequence creates a nonisostatic set from an isostatic one (because a $K_{6,6}$ is formed exactly then). I'm not sure how much this changes as we change the sequence of 2extensions, nor even how much freedom we have in performing these 2extensions if we want to go from $K_6$ to $K_{7,6}$. I suspect that the key is in the formation of the cycle $K_{6,6}$.
Below I share what I did in Mathematica; perhaps the code will be helpful for further experimentation. It is a bit tedious, so search this page for "G6" if you want to skip to the exciting part.
First, I wrote some ugly code to compute a 4 dimensional rigidity matrix. No doubt this can be improved.
(* p is a list of 4 dimensional vectors corresponding to vertex positions,
E is a list of the pairs of vertices {i,j} (with i<j) that are joined by edges *)
RigidityMatrix4[p_, E_] :=
Module[{e = Length[E], nd = Length[p] Length[p[[1]]], px, py, pz, pw},
Table[
px = p[[E[[j, 1]], 1]]  p[[E[[j, 2]], 1]];
py = p[[E[[j, 1]], 2]]  p[[E[[j, 2]], 2]];
pz = p[[E[[j, 1]], 3]]  p[[E[[j, 2]], 3]];
pw = p[[E[[j, 1]], 4]]  p[[E[[j, 2]], 4]];
Insert[Insert[Insert[Insert[
Insert[Insert[Insert[Insert[
Table[0, {nd  8}], px, 4 E[[j, 1]]  3], py,
4 E[[j, 1]]  2], pz, 4 E[[j, 1]]  1], pw, 4 E[[j, 1]]],
px, 4 E[[j, 2]]  3], py, 4 E[[j, 2]]  2], pz,
4 E[[j, 2]]  1], pw, 4 E[[j, 2]]], {j, e}]]
Here's a function to create the list of edges corresponding to a complete graph:
makecompletegraph[l_] := Reap[Do[If[i != j, Sow[{i, j}]], {i, l}, {j, i, l}]][[2, 1]]
Now I begin by creating $K_6$ and deleting the edge {5,6}. The output is a list of the edges as pairs of vertices:
G = makecompletegraph[6][[1 ;; 14]]
{{1, 2}, {1, 3}, {1, 4}, {1, 5}, {1, 6}, {2, 3}, {2, 4}, {2, 5}, {2,
6}, {3, 4}, {3, 5}, {3, 6}, {4, 5}, {4, 6}}
I next compute the number of nontrivial infinitesimal motions of a generic embedding of G and the number of redundancies among its edges:
R = RigidityMatrix4[RandomReal[{0, 1}, {6, 4}], G];
{MatrixRank[NullSpace[R]]  10, Length[G]  MatrixRank[R]}
{0,0}
Thus G is isostatic.
I now perform the first 2extension, by deleting the edges {1,2} and {3,4} and connecting a new vertex 7 to vertices 1 through 6, and check that the resulting graph "G1" is isostatic:
G1 = Join[Select[G, # != {1, 2} && # != {3, 4} &], Table[{i, 7}, {i, 6}]]
R1 = RigidityMatrix4[RandomReal[{0, 1}, {7, 4}], G1];
{MatrixRank[NullSpace[R1]]  10, Length[G1]  MatrixRank[R1]}
{{1, 3}, {1, 4}, {1, 5}, {1, 6}, {2, 3}, {2, 4}, {2, 5}, {2, 6}, {3,
5}, {3, 6}, {4, 5}, {4, 6}, {1, 7}, {2, 7}, {3, 7}, {4, 7}, {5,
7}, {6, 7}}
{0,0}
In the second step, I remove {1,3} and {2,4} and attach vertex 8 to vertices 1 through 6 to form G2, which is also isostatic:
G2 = Join[Select[G1, # != {1, 3} && # != {2, 4} &], Table[{i, 8}, {i, 6}]]
R2 = RigidityMatrix4[RandomReal[{0, 1}, {8, 4}], G2];
{MatrixRank[NullSpace[R2]]  10, Length[G2]  MatrixRank[R2]}
{{1, 4}, {1, 5}, {1, 6}, {2, 3}, {2, 5}, {2, 6}, {3, 5}, {3, 6}, {4,
5}, {4, 6}, {1, 7}, {2, 7}, {3, 7}, {4, 7}, {5, 7}, {6, 7}, {1,
8}, {2, 8}, {3, 8}, {4, 8}, {5, 8}, {6, 8}}
{0,0}
Next {1,5} and {2,6} are removed and vertex 9 is attached to vertices 1 through 6 forming the isostatic G3:
G3 = Join[Select[G2, # != {1, 4} && # != {2, 5} &], Table[{i, 9}, {i, 6}]]
R3 = RigidityMatrix4[RandomReal[{0, 1}, {9, 4}], G3];
{MatrixRank[NullSpace[R3]]  10, Length[G3]  MatrixRank[R3]}
{{1, 5}, {1, 6}, {2, 3}, {2, 6}, {3, 5}, {3, 6}, {4, 5}, {4, 6}, {1,
7}, {2, 7}, {3, 7}, {4, 7}, {5, 7}, {6, 7}, {1, 8}, {2, 8}, {3,
8}, {4, 8}, {5, 8}, {6, 8}, {1, 9}, {2, 9}, {3, 9}, {4, 9}, {5,
9}, {6, 9}}
{0,0}
{1,5} and {2,6} are removed; vertex 10 is attached, G4 is isostatic:
G4 = Join[Select[G3, # != {1, 5} && # != {2, 6} &], Table[{i, 10}, {i, 6}]]
R4 = RigidityMatrix4[RandomReal[{0, 1}, {10, 4}], G4];
{MatrixRank[NullSpace[R4]]  10, Length[G4]  MatrixRank[R4]}
{{1, 6}, {2, 3}, {3, 5}, {3, 6}, {4, 5}, {4, 6}, {1, 7}, {2, 7}, {3,
7}, {4, 7}, {5, 7}, {6, 7}, {1, 8}, {2, 8}, {3, 8}, {4, 8}, {5,
8}, {6, 8}, {1, 9}, {2, 9}, {3, 9}, {4, 9}, {5, 9}, {6, 9}, {1,
10}, {2, 10}, {3, 10}, {4, 10}, {5, 10}, {6, 10}}
{0,0}
{1,6} and {2,3} are removed; vertex 11 is attached, G5 is isostatic:
G5 = Join[Select[G4, # != {1, 6} && # != {2, 3} &], Table[{i, 11}, {i, 6}]]
R5 = RigidityMatrix4[RandomReal[{0, 1}, {11, 4}], G5];
{MatrixRank[NullSpace[R5]]  10, Length[G5]  MatrixRank[R5]}
{{3, 5}, {3, 6}, {4, 5}, {4, 6}, {1, 7}, {2, 7}, {3, 7}, {4, 7}, {5,
7}, {6, 7}, {1, 8}, {2, 8}, {3, 8}, {4, 8}, {5, 8}, {6, 8}, {1,
9}, {2, 9}, {3, 9}, {4, 9}, {5, 9}, {6, 9}, {1, 10}, {2, 10}, {3,
10}, {4, 10}, {5, 10}, {6, 10}, {1, 11}, {2, 11}, {3, 11}, {4,
11}, {5, 11}, {6, 11}}
{0,0}
{3,5} and {4,6} are removed and vertex 12 is attached. The resulting graph G6 is not isostatic! Of course, this is because a $K_{6,6}$ is formed.
G6 = Join[Select[G5, # != {3, 5} && # != {4, 6} &], Table[{i, 12}, {i, 6}]]
R6 = RigidityMatrix4[RandomReal[{0, 1}, {12, 4}], G6];
{MatrixRank[NullSpace[R6]]  10, Length[G6]  MatrixRank[R6]}
{{3, 6}, {4, 5}, {1, 7}, {2, 7}, {3, 7}, {4, 7}, {5, 7}, {6, 7}, {1,
8}, {2, 8}, {3, 8}, {4, 8}, {5, 8}, {6, 8}, {1, 9}, {2, 9}, {3,
9}, {4, 9}, {5, 9}, {6, 9}, {1, 10}, {2, 10}, {3, 10}, {4, 10}, {5,
10}, {6, 10}, {1, 11}, {2, 11}, {3, 11}, {4, 11}, {5, 11}, {6,
11}, {1, 12}, {2, 12}, {3, 12}, {4, 12}, {5, 12}, {6, 12}}
{1,1}
Just for completeness, I performed the last 2extension; removing {3,6} and {4,5} and attaching vertex 13. You can see this is $K_{7,6}$:
G7 = Join[Select[G6, # != {3, 6} && # != {4, 5} &], Table[{i, 13}, {i, 6}]]
R7 = RigidityMatrix4[RandomReal[{0, 1}, {13, 4}], G7];
{MatrixRank[NullSpace[R7]]  10, Length[G7]  MatrixRank[R7]}
{{1, 7}, {2, 7}, {3, 7}, {4, 7}, {5, 7}, {6, 7}, {1, 8}, {2, 8}, {3,
8}, {4, 8}, {5, 8}, {6, 8}, {1, 9}, {2, 9}, {3, 9}, {4, 9}, {5,
9}, {6, 9}, {1, 10}, {2, 10}, {3, 10}, {4, 10}, {5, 10}, {6,
10}, {1, 11}, {2, 11}, {3, 11}, {4, 11}, {5, 11}, {6, 11}, {1,
12}, {2, 12}, {3, 12}, {4, 12}, {5, 12}, {6, 12}, {1, 13}, {2,
13}, {3, 13}, {4, 13}, {5, 13}, {6, 13}}
{2,2}

answered Nov 3 '11 at 19:23

