Flexibility, NAC-colorings and stable cuts

A realization of a graph in the plane is called flexible if it can be continuously deformed while preserving the distances between adjacent vertices, otherwise rigid. For a graph, either almost all its realizations are rigid, or almost all are flexible. Hence, we can speak about (generically) rigid/flexible graphs. A graph is called minimally rigid if removing any edge yields a flexible graph.

Regarding the non-generic behavior, it was proven that a connected graph admits a flexible (non-generic) realization if and only if it has so called NAC-coloring, which is a surjective edge coloring by red and blue such that every cycle is either monochromatic or contains at least two red and two blue edges. The question whether a graph has a NAC-coloring is NP-complete. In this talk we show that this is not the case for minimally rigid graphs using a result from extremal graph theory about stable cuts by Le and Pfender. We also prove that every flexible graph has a stable cut and discuss some bound on the number of NAC-colourings.