Is this braced heptagon a rigid graph?

Question

In Mathematica, GraphData[{"UnitDistance", {21, 2}}]

Is this 42-edge graph rigid? It has chromatic number 4. If it was floppy, that might make it an interesting tool in high-chromatic graph studies.

The current record for heptagon bracing is 59, so this would beat that.

Answer 1

The graph is rigid. In fact I will show that the following $35$-edge graph formed by deleting the two interior vertices of one triangle is (minimally) rigid:

We first need to find a parametrisation of the vertices of the graph with as few parameters as possible (that relate to metrics like lengths and angles); three parameters suffice. Fix $A$ and $B$ in the diagram below, set as parameters the angles $\alpha_1,\alpha_2,\alpha_3$ that the vectors $\vec{A0},\vec{B1},\vec{B2}$ make with $\vec{AB}$, then construct each of the remaining numbered points in order as the point that is a distance $1$ away from two already-determined points. (See the program at the end of this answer for the exact construction sequence.)

Define the function $f:\mathbb R^3\to\mathbb R^3$ as $$f(\alpha_1,\alpha_2,\alpha_3)=(d(11,12),d(13,14),d(15,2))$$ i.e. it returns the lengths of the three thick edges, which are not created as part of the construction but are in the graph. Let the parameters corresponding to the regular braced heptagon be $\alpha_1^*,\alpha_2^*,\alpha_3^*$; clearly $f(\alpha_1^*,\alpha_2^*,\alpha_3^*)=(1,1,1)$. To check the rigidity of the ($35$-edge) graph, we construct the Jacobian matrix $J$ of $f$ at $(\alpha_1^*,\alpha_2^*,\alpha_3^*)$; if it has full rank we can immediately conclude that it is (infinitesimally or first-order) rigid.

It turns out that $J$ is a $3×3$ matrix with rank $2$. This does not mean that the graph is not rigid; we still have to analyse the behaviour of $f$ along the infinitesimal motion associated with this rank-deficient $J$. Such a motion is given by an element of the nullspace of $J$; suppose this element is $(\delta_1,\delta_2,\delta_3)$. Define $$g(t)=f(\alpha_1^*+t\delta_1,\alpha_2^*+t\delta_2,\alpha_3^*+t\delta_3)$$ When we plot $g$ for $t$ around zero we get the following graph (blue, red and green lines represent the three coordinates in order):

The lengths of all three thick edges are individually on the same side of $1$. Together with the result from the Jacobian matrix, we infer that said lengths are not $1$ in a punctured neighbourhood of $(\alpha_1^*,\alpha_2^*,\alpha_3^*)$, so the $35$-edge graph is (second-order) rigid.

As a final note, it can be easily shown that the $35$-edge graph is a Laman graph by means of a Henneberg construction, so no edges can be removed without making the graph flexible.

---

#!/usr/bin/env python3
from mpmath import *
mp.dps = 100

def cu(z1, z2):
    # Constructs the point at a distance of 1 from z1 and z2,
    # left of the line from z1 to z2.
    m = (z1 + z2) / 2
    d, theta = polar(z2 - z1)
    return m + sqrt(1 - d * d / 4) * expj(theta + pi / 2)

def f(a1, a2, a3):
    # Progressive construction of the graph's vertices.
    # Returns the distances between three pairs of vertices that are
    # not directly related in the construction but are still linked
    # by an edge.
    A = mpf(0)
    B = mpf(1)
    p0 = expj(a1)
    p1 = 1+expj(a2)
    p2 = 1+expj(a3)
    p3 = cu(p1, p0)
    p4 = cu(B, p1)
    p5 = cu(p0, p3)
    p6 = cu(p2, p5)
    p7 = cu(p4, p6)
    p8 = cu(p6, p2)
    p9 = cu(p8, A)
    p10 = cu(A, p9)
    p11 = cu(p0, p7)
    p12 = cu(p9, p7)
    p13 = cu(p12, p1)
    p14 = cu(p5, p10)
    p15 = cu(p13, p14)
    return abs(p11-p12), abs(p13-p14), abs(p15-p2)

# Known parameters at the intended solution. a2 is exact, 1.43262130059...
a1 = 5*pi/7
a2 = phase(polyroots([7, 28, 70, 133, 203, 259, 281, 259, 203, 133, 70, 28, 7])[10])
a3 = 2*pi/7

# Jacobian matrix of f
def fderiv(i, j):
    ff = lambda x, y, z: f(x,y,z)[i]
    dvec = tuple(int(n == j) for n in range(3))
    return diff(ff, (a1,a2,a3), dvec)
J = matrix([[fderiv(i, j) for j in range(3)] for i in range(3)])

# J is rank-deficient at the reference solution,
# i.e. the framework is not first-order (infinitesimally) rigid.
# Not to worry. Analyse f's behaviour along the one infinitesimal motion...
_, Sigma, V = svd(J)
nprint(chop(Sigma))
da1, da2, da3 = V[2,:]
def g(z):
    return f(a1+z*da1, a2+z*da2, a3+z*da3)

# The lengths of the three "test rods" are individually on the same side of 1
# for sufficiently small multiples of the infinitesimal motion.
# This shows that the graph is (second-order) rigid.
plot([lambda z: g(z)[0], lambda z: g(z)[1], lambda z: g(z)[2]], [-0.1, 0.1])

---

The graphs above were drawn with the help of a script in my Dounreay repository. Run ./drawgraph.py heptagon in the folder containing drawgraph.py to reproduce the full $42$-edge graph; the above pictures are the result of tweaking in Inkscape.

---

Removing two consecutive vertices of one of the inner stars leads to a first-order rigid graph in either case (the determinant of $J$ is non-zero):

A = mpf(0)
B = mpf(1)
p0 = expj(a1)
p1 = 1+expj(a2)
p2 = 1+expj(a3)
p3 = cu(p1, p0)
p4 = cu(B, p1)
p5 = cu(p0, p3)
p6 = cu(p2, p5)
p7 = cu(p4, p6)
p8 = cu(p6, p2)
p9 = cu(p8, A)
p10 = cu(p3, p8)
p11 = cu(p9, p7)
p12 = cu(p11, p1)
p13 = cu(p12, p5)
p14 = cu(p0, p7)
p15 = cu(p13, p2)
p16 = cu(p14, p10)
return abs(p11-p14), abs(p12-p15), abs(p15-p16)

A = mpf(0)
B = mpf(1)
p0 = expj(a1)
p1 = 1+expj(a2)
p2 = 1+expj(a3)
p3 = cu(p1, p0)
p4 = cu(B, p1)
p5 = cu(p0, p3)
p6 = cu(p2, p5)
p7 = cu(p4, p6)
p8 = cu(p6, p2)
p9 = cu(p8, A)
p10 = cu(A, p9)
p11 = cu(p0, p7)
p12 = cu(p3, p8)
p13 = cu(p10, p4)
p14 = cu(p5, p10)
p15 = cu(p14, p2)
p16 = cu(p11, p12)
return abs(p12-p13), abs(p13-p16), abs(p16-p15)

Answer 2

My proof was written up in a Mathematica. I've made a copy available on Google-Drive both as a Mathematica notebook (NewHeptagon-Draft1.nb) and as a static pdf (NewHeptagon-Draft1.pdf). Since the version of Mathematica I was using didn't have GraphData[{"UnitDistance", {21, 2}}] I had to regenerate the graph from just its picture so that's embedded in there as well.