# Is every 1-million-connected graph rigid in 3D?

It is an old result that every $$6$$-connected graph is rigid in $$\mathbb{R}^2$$:

Lovász, László, and Yechiam Yemini. "On generic rigidity in the plane." SIAM Journal on Algebraic Discrete Methods 3, no. 1 (1982): 91-98. DOI.

It is natural to hope that sufficiently high connectivity implies rigidity in $$\mathbb{R}^3$$.

Q. Is it known that there is some $$k$$ such that any $$k$$-connected graph is generically rigid in $$\mathbb{R}^3$$?

Informally, $$G$$ is rigid if the distances between vertices connected in $$G$$ determine all the distances between vertices not connected in $$G$$. More formally, $$G$$ is generically rigid in $$\mathbb{R}^d$$ if every generic representation in $$\mathbb{R}^d$$ is infinitesimally rigid—no infinitesimal length-preserving velocities (if they exist) can be extended. An embedded graph representation (a framework) is generic if the coordinates of its configuration do not satisfy any non-trivial algebraic equation with rational coefficients.

There have been recent advances in 3D rigidity and I am unclear on the current status of this question Q.

• For the reader: $k$-connected means that there are $>k$ vertices, and removing any $< k$ vertices yields a connected graph.
– YCor
May 9, 2021 at 11:25
• @FedorPetrov: I believe the implication direction is: If infinitesimally rigid in $\mathbb{R}^3$, then $m \ge 3 n - 6$, where $m$ is the number of edges and $n$ the number of vertices. It is iff in the plane (with $m \ge 2 n - 3$). The flexible, generic double-banana satisfies $m = 3n-6$. May 9, 2021 at 12:46
• I do not think that even on the plane it is iff: glue two large complete graphs by a vertex. Actually, if for certain $k$ vertices there are more than $3k-6$ edges between them, and total number of edges is $3n-6$, it can not be rigid (analogously in dimension 2). May 9, 2021 at 14:24
• @FedorPetrov: Sorry, my misinterpretation of JieGao lecture notes: It is, instead of $m$, the rank of the rigidity matrix $R$---"disregarding global translation and rotation, the framework $G(P)$ is infinitesimally rigid if and only if rank$(R) = 2n − 3$." PDF. May 9, 2021 at 14:39
• Adding nothing but a physical example to what has already been described. A door is a physical realization of an infinitely connected graph that is not rigid. May 10, 2021 at 1:56

I think this is still an open problem, but recent work of Clinch, Jackson, and Tanigawa (almost) shows every $$12$$-connected graph is generically rigid in $$\mathbb{R}^3$$.
In that paper, they prove that $$12$$-connectivity is sufficient to force rigidity in the $$C_2^1$$-cofactor matroid (see the paper for precise definitions). In an earlier paper, the same authors showed that the $$C_2^1$$-cofactor matroid is the unique maximal abstract $$3$$-rigidity matroid. A long-standing conjecture in rigidity theory is that the unique maximal abstract $$3$$-rigidity matroid is in fact the generic $$3$$-dimensional rigidity matroid. If you believe this conjecture, then the answer to your quesiton is yes, with one million replaced with $$12$$.
I am afraid that no. Take two half-planes with a common boundary line $$a$$, and many points both on $$a$$ and in these half-planes. Join by edges all pairs of points in the same half-plane. Now rotate one of the half-planes around $$a$$.