I figured out a unit distance embedding for the McGee graph.

Bram Cohen asked me if it's rigid. I had a hard enough time figuring out this one embedding. If some points can move around, I might want to add some more edges. But that would break some existing records in chromatic graphs, if it's not rigid. If it is rigid, then it's a girth 7 rigid object.

Is it rigid?

McGee graph

  • $\begingroup$ What did it mean for a graph to be rigid again? $\endgroup$
    – mrm
    Oct 17, 2015 at 8:45
  • $\begingroup$ If it isn't rigid, some of the points can be moved some to distort the graph. $\endgroup$
    – Ed Pegg
    Oct 17, 2015 at 16:21

1 Answer 1


[Finite deformations of McGee graph maintaining unit edge lengths

The graph is not rigid. To check that it is not infinitesimally rigid, we can attribute a linear and angular velocity to each edge (giving us 3 × 36 = 108 parameters), and then compute the different velocities that these induce on each vertex. Since every vertex has three edges incident on it, we get three potentially different two-dimensional velocity vectors for each vertex, and if we take the difference of two pairs, we get four quantities that must be zero for each vertex if the graph holds together, for a total of 24 × 4 = 96.

The 96 × 108 matrix associated with this linear system has a 12-dimensional null space; this is what you would expect from simply counting the row and column dimensions, but of course the answer might have been different if there had been some redundancy in the equations. Since there is a 3-parameter family of rigid motions that don't change the shape of the graph at all, that leaves a 9-parameter family of infinitesimal deformations of the graph that don't translate or rotate it overall (say, those that fix one of the edges at the centre), but change its shape while preserving all the edge lengths.

Are there also finite deformations? Yes! The easiest way to find a specific trajectory through the configuration space is to make some further choices that whittle down the 9-parameter space to just one parameter: in the calculations I tried, I fixed both the vertical and horizontal edges at the centre, limited the two oblique edges at the centre to rotations only, and required them to rotate by equal angles in opposite directions. That left 12 - 2 × 3 - 2 × 2 - 1 = 1 degree of freedom. I then numerically integrated a trajectory through the configuration space for the edges that met those additional constraints, as well as the need to keep the three edge-induced velocities at each vertex equal.

There was also some freedom to parameterise the trajectory with time, so I chose a parameterisation such that the total kinetic energy of all the edges remained constant.

  • 2
    $\begingroup$ Gorgeous animation. Quite lovely. $\endgroup$
    – Ed Pegg
    Oct 15, 2016 at 3:11

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .