Minimum degree conditions for graph rigidity

DOI10.1112/BLMS.70279MaRDI QIDQ6864301zbMATH OpenFDO

Authors Michael Krivelevich, Alan Lew, Peleg Michaeli

Publication date 4 February 2026

Published in Bulletin of the London Mathematical Society (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1112/BLMS.70279

\(d\)-connected graph \(d\)-dimensional framework generic embedding graph rigidity minimum degree Regularity Lemma

Planar graphs; geometric and topological aspects of graph theory (05C10) Rigidity and flexibility of structures (aspects of discrete geometry) (52C25)

Review text

This paper is concerned with the rigidity of \(d\)-dimensional frameworks. It seeks to give a lower bound on the minimum degree of a graph which would guarantee that any generic embedding of the graph into \(\mathbb{R}^d\) is rigid. In this case, such graphs are called \(d\)-rigid.\N\NIt is well-known that if a graph is \(d\)-rigid, then it must be \(d\)-connected as well. On the other hand, if the minimum degree of an \(n\)-vertex graph satisfies the following inequality, \(\delta(G)\ge \frac{n+d}{2}-1\), then it is surely \(d\)-connected. From the rigidity matrix, it is also known that any \(d\)-rigid graph must satisfy the inequality \(|E|\ge dn-\binom{d+1}{2}\), which is fulfilled if \(\delta(G)\ge 2d-\frac{d(d+1)}{n}\). These observations led to the following conjecture of this paper.\N\NConjecture. Let \(n>d\ge 1\). If \(G\) is an \(n\)-vertex graph with \(\delta(G)\ge \max \left \{ \frac{n+d}{2}-1, 2d-\frac{d(d+1)}{n} \right \}\), then \(G\) is \(d\)-rigid.\N\NThis conjecture generalizes and is analogous to some earlier conjectures (see Conjecture 1.16 in [\textit{M. Krivelevich} et al., J. Comb. Theory, Ser. B 175, 126--170 (2025; Zbl 1572.05230)] and Conjecture 38 in [\textit{B. Jackson} et al., J. Comb. Theory, Ser. B 121, 432--462 (2016; Zbl 1354.15018)]) and in this paper the authors make advance towards this conjecture by proving it for small \(d\) values (Theorem 1.1), namely for \(d\le \frac{\sqrt{8n-15}-1}{4}\) relying on a recent result of \textit{S. Villányi} [J. Comb. Theory, Ser. B 173, 1--13 (2025; Zbl 1564.05067)].\N\NThey also prove a result (Theorem 1.2) for larger \(d\) values, which is optimal up to a factor of \(2\). They divide their argument into two parts: whether \(G\) is close to being bipartite or not. In the second case, they use the Regularity Lemma, too. As a corollary of this second theorem, they obtain a new result (Theorem 1.3) regarding the pseudoachromatic number of a graph with given minimum degree, which might be of independent interest.\N\NThe authors also include an important note that points out that independently of them \textit{T. Jordán} et al. [``Degree sum conditions for graph rigidity, Preprint, \url{arXiv:2510.25689}] further improved their main results. Namely, their conjecture holds for \(d\le \frac{n}{29}\), and they also extended their second result (Theorem 1.2) to all \(d\) values.

Cites work

This page was built for publication: Minimum degree conditions for graph rigidity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6864301)