cp's OEIS Frontend

All the Laman graphs (in other words, minimally rigid graphs) can be constructed by the inductive Henneberg construction, i.e., a sequence of Henneberg steps starting from K_2. A new vertex added by a Henneberg move is connected with two or three of the previously existing vertices. Hence, the chromatic number of a Laman graph can be 2, 3 or 4. One can hypothesize that the set of 3-chromatic Laman graphs is the largest and that bipartite graphs are relatively rare. The first nontrivial bipartite Laman graph is K_{3,3}. An infinite sequence of such graphs can be obtained from K_{3,3} by Henneberg moves of the first type (i.e., adding a vertex and connecting it with two of the existing vertices from the one part).

A 2n-vertex graph is (3/2,2)-sparse if every subgraph with k vertices has at most (3/2)k-2 edges, and (3/2,2)-tight if in addition it has exactly 3n-2 edges; see Lee and Streinu (2008). These graphs represent two-dimensional mechanical systems formed by 2n rigid bodies (links), connected at joints where exactly two links are pinned together and can rotate relative to each other, with the entire system having one degree of freedom and having no rigid subsystems. The vertices of the graph represent links and the edges represent joints.