2024/12/20 by Clinch, Katie, Garamvölgyi, Dániel, Haslegrave, John +3 · 2 citations
#05C15 #52C25 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2412.16018
A (2-dimensional) realisation of a graph G is a pair (G,p), where p maps the vertices of G to ℝ2. A realisation is flexible if it can be continuously deformed while keeping the edge lengths fixed, and rigid otherwise. Similarly, a graph is flexible if its generic realisations are flexible, and rigid otherwise. We show that a minimally rigid graph has a flexible realisation with positive edge lengths if and only if it is not a 2-tree. This confirms a conjecture of Grasegger, Legerský and Schicho. Our proof is based on a characterisation of graphs with n vertices and 2n-3 edges and without stable cuts due to Le and Pfender. We also strengthen a result of Chen and Yu, who proved that every graph with at most 2n-4 edges has a stable cut, by showing that every flexible graph has a stable cut. 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.