What rigid graphs can be decomposed into triangles such that each edge is in exactly one triangle?

Question

Is there a general algorithm/condition to tell if a graph can be decomposed into triangles such that each edge is in exactly one triangle (the graph $G$ has a set of subgraphs such that each subgraph is isomorphic to $K_3$, and each edge of G appears in exactly one of the triangles)?

Is it possible to enumerate the graphs that have an infinitesimally rigid embedding in $R^3$, and can also be decomposed into triangles up to a certain number of nodes?

Necessary conditions are that the number of edges in each graph must be divisible by 3, and the degree of each node must be even, but I don't think those conditions are sufficient.

One family of graphs that meets these conditions are the graphs formed by the edges of all n-gonal bipyramids where n is even.

For my PhD I built a robot composed of discrete triangles assembled into an octahedron shape. I am curious what other robots I could make using a similar system. (see image)

Robot image

Answer 1

If you take any graph without triangles which has all vertices of degree 3 (a cubic graph) and form the line graph of that cubic graph, then the resulting graph will have all edges in exactly one of the triangles formed around where the cubic vertices were.

For instance; taking the pentagonal prism:

It has the following graph as its line graph, which can be seen to have every edge in one triangle:

Although it is difficult in general to verify that a graph has this property (if it has a suitable number of vertices and edges), it is straightforward to create more simply by locating some vertices which are not already joined to all others and adding either a triangle between those vertices or adding a new vertex forming triangles with it and pairs of vertices from the original graph.

For instance, your hexagonal bipyramid can either be formed by adding a vertex of degree 6 as part of 3 triangles to a windmill, or a vertex of degree 4 to a 7-vertex graph or a triangle to an 8-vertex graph. All of the base graphs have vertices of degree 2 though, so it is probably best to generate all graphs and then do your rigidity check.