Stable Cuts, NAC‐Colourings and Flexible Realisations of Graphs

ABSTRACT A (2‐dimensional) realisation of a graph is a pair , where maps the vertices of to . A realisation is flexible if it can be continuously deformed while keeping the edge lengths fixed, and rigid otherwise. We say that is rigid if every generic realisation of is rigid; otherwise, is flexible. In this paper, we investigate the relationship between stable cuts and graphs which are either flexible or admit a flexible (not necessarily generic) realisation with positive edge lengths. We strengthen a result of Chen and Yu, who proved that every ‐vertex graph with at most edges has a stable cut, by showing that every flexible graph has a stable cut. The existence of a stable cut is a sufficient, but not necessary, condition for a flexible realisation to exist. Using a result of Le and Pfender on stable cuts, we prove a conjecture of Grasegger, Legerský and Schicho that characterises the minimally rigid graphs that admit a flexible realisation. Additionally, we investigate the number of NAC‐colourings in various graphs. A NAC‐colouring is a type of edge colouring introduced by Grasegger, Legerský and Schicho, who showed that the existence of such a colouring characterises the existence of a flexible realisation with positive edge lengths. We provide an upper bound on the number of NAC‐colourings for arbitrary graphs, and construct families of graphs, including rigid and minimally rigid ones, for which this number is exponential in the number of vertices.