cp's OEIS Frontend

A graph G=(V,E) is (3,6)-tight if |E|=3|V|-6 and for every subgraph G'=(V',E') with at least 3 vertices |E'|<=3|V'|-6.

Every minimally rigid graph in 3D (A328419) is (3,6)-tight.

All minimally rigid graphs in 3D on n vertices can be constructed from the minimally rigid graphs in 3D on n-1 vertices by use of three types of constructions called the Henneberg constructions. In the first type a new vertex is added to the graph and three new edges are added connecting the new vertex to three different vertices which were already part of the graph. In the second type of construction, two adjacent vertices, say v_1 and v_2, are selected. The edge between v_1 and v_2 is deleted. A new vertex w is added to the graph, as well as the edges (v_1,w), (v_2,w), (v_3,w), and (v_4,w), where v_3 and v_4 are other vertices of the graph. The third construction chooses two pairs of adjacent vertices v_1,v_2 and v_3,v_4, where v_3 might be equal to v_2. The edges (v_1,v_2) and (v_3,v_4) are deleted. A new vertex w is added to the graph. If v_2!=v_3, the edges (v_1,w), (v_2,w), (v_3,w), (v_4,w), and (v_5,w) are added, where v_5 is another vertex of the graph. If v_2=v_3, other two vertices v_5,v_6 are chosen and the edges (v_1,w), (v_2,w),(v_4,w), (v_5,w), and (v_6,w) are added.

The first two constructions preserve rigidity whereas the third does not necessarily preserve rigidity. Nevertheless the third construction is needed to get all minimally rigid graphs in 3D. Up to 11 vertices the first two constructions suffice.

Each of these three constructions adds one to the number of vertices and three to the number of edges, i.e., all those graphs have 3n-6 edges for n vertices. Not all graphs with that number of edges are minimally rigid in 3D.

Every minimally rigid graph in 3D is (3,6)-tight (A374745). - Georg Grasegger, Oct 17 2024