Degree Sum Conditions for Graph Rigidity

Basic Information

• Paper ID: 2510.25689
• Title: Degree Sum Conditions for Graph Rigidity
• Authors: Tibor Jordán (ELTE Eötvös Loránd University), Xuemei Liu (Northwestern Polytechnical University), Soma Villányi (ELTE Eötvös Loránd University)
• Classification: math.CO (Combinatorics)
• Publication Date: October 23, 2025 (arXiv preprint)
• Paper Link: https://arxiv.org/abs/2510.25689

Abstract

This paper investigates sufficient conditions for generic rigidity of graphs through two types of degree conditions: (i) minimum degree δ(G), and (ii) parameter η(G) = min_{uv∉E}(deg(u) + deg(v)) (minimum degree sum of non-adjacent vertex pairs). The research aims to find the minimum integers f(n,d) and g(n,d) such that n-vertex graphs satisfying the corresponding degree conditions are rigid in R^d.

Main contributions include:

1. Proof of the conjecture by Krivelevich et al.: f(n,d) ≤ n/2 + d - 1 for all n,d
2. Exact result f(n,d) = ⌈(n+d-2)/2⌉ for n ≥ 29d
3. Proof that g(n,d) ≤ n + 3d - 3, and establishment of g(n,d) = n + d - 2 for n ≥ d(d+2)
4. Complete determination of exact values of f(n,d) and g(n,d) for d = 2,3
5. Application to random graphs: proof that Erdős-Rényi random graph G(n,1/2) is almost surely rigid in R^d where d ~ (7/32)n, providing the first linear lower bound

Research Background and Motivation

Problem Background

Rigidity Theory Foundation: A d-dimensional bar-and-joint framework (G,p) consists of a simple graph G=(V,E) and a mapping p: V → R^d. A framework is rigid if there exists no continuous motion preserving all edge lengths while changing distances between some non-adjacent vertex pairs. For generic frameworks (vertex coordinates algebraically independent over Q), the rigidity property is determined by graph G, termed G being d-rigid.

Fundamental Theory:

• d-rigid graphs must be d-connected
• An n-vertex d-rigid graph requires at least dn - d(d+1)/2 edges
• d(d+1)-connected graphs are necessarily d-rigid

Research Motivation

1. Theoretical Importance: Rigidity theory is an interdisciplinary field spanning combinatorial optimization, topology, and discrete geometry, with important applications in sensor network localization, structural engineering, and molecular modeling
2. Limitations of Existing Work:
   • Krivelevich, Lew and Michaeli 11,12 established f(n,d) ≤ (n + 3d log n)/2
   • For sufficiently large n (n ≥ Ω(d) log² n), improved to f(n,d) ≤ n/2 + d - 1
   • However, the log n dependency and small n cases remain unresolved
3. Core Questions:
   • Question 1: What is the exact value of f(n,d)?
   • Question 2: What is the value of the more general parameter g(n,d) (based on degree sum conditions)?
   • Two key conjectures await proof (Conjectures 1.1 and 1.4)
4. Methodological Innovation Needs: Existing methods rely primarily on connectivity and probabilistic arguments; new matroid-theoretic tools and structural properties are needed

Core Contributions

1. Resolution of Conjecture 1.1: Proof that f(n,d) ≤ n/2 + d - 1 for all n,d (K=1), removing restrictions on n
2. Exact Threshold Theorem: For n ≥ 29d, proof that f(n,d) = ⌈(n+d-2)/2⌉ (Theorem 1.3), significantly improving the previous condition n ≥ d(2d+1)+2
3. General Bounds for Degree Sum Conditions:
   • Proof that g(n,d) ≤ n + 3d - 3 (Theorem 1.6)
   • Establishment of exact value g(n,d) = n + d - 2 for n ≥ d(d+2) (Theorem 1.7)
4. Complete Characterization in Low Dimensions:
   • d=3: Complete determination of g(n,3) for all n, with only 4 exceptional graphs (W₅, B₆, C¹₇, C²₇)
   • d=2: Derivation from d=3 results via coning technique
   • Verification of Conjecture 1.4 for d=2,3
5. Random Graph Application: Proof that G(n,1/2) is almost surely rigid in d = 7n/32 - √(15n log n)/16 dimensional space, providing the first linear lower bound (previous best was O(n/log n))
6. Methodological Contributions:
   • Introduction of new parameter r⁺_d(G) = r_d(G^w) - r_d(G) for matroid analysis
   • Development of probabilistic techniques for rank contribution
   • Pure combinatorial proofs replacing some probabilistic arguments
7. Global Rigidity Corollaries: Through known lifting theorems from rigidity to global rigidity, automatic derivation of corresponding results for global rigidity in R^{d-1}

Methodology Details

Task Definition

Core Problem Formalization:

Given positive integers n (number of vertices) and d (dimension), determine:

1. f(n,d): The minimum integer such that all n-vertex graphs G satisfying δ(G) ≥ f(n,d) are rigid in R^d
2. g(n,d): The minimum integer such that all n-vertex graphs G satisfying η(G) ≥ g(n,d) are rigid in R^d

where η(G) = min_{uv∉E}(deg_G(u) + deg_G(v))

Known Bounds:

• Lower bound: ⌈(n+d-2)/2⌉ ≤ f(n,d) (from d-connectivity)
• Relationship: f(n,d) ≤ ⌈g(n,d)/2⌉ (since η(G) ≥ 2δ(G))

Core Technical Framework

1. Matroid-Theoretic Tools

d-dimensional Generic Rigidity Matroid R^d(G):

• Defined on edge set E(G)
• Rank function r_d(G) satisfies: r_d(G) = d|V| - (d+1 choose 2) if and only if G is d-rigid
• Degrees of freedom: dof_d(G) = d|V| - (d+1 choose 2) - r_d(G)

Key Concepts:

• R^d-closure: Maximum graph obtained by adding R^d-linked edge pairs
• R^d-bridge: Edge whose deletion decreases rank by 1
• R^d-circuit: Minimal non-independent edge set

Whiteley's Coning Theorem (Theorem 2.5):

G is R^d-independent (rigid) ⟺ G^w is R^{d+1}-independent (rigid)

where G^w is the cone graph of G (adding new vertex w connected to all original vertices)

2. New Parameter r⁺_d(G)

Definition:

r⁺_d(G) = r_d(G^w) - r_d(G)

Key Properties (Lemma 3.4):

r⁺_d(G)(δ - d + 2) ≤ d(n - d + 1)

In particular, if δ ≥ (n+d-2)/2, then r⁺_d(G) < 2d

Recursive Relation (Lemma 3.1):

r⁺_{d+1}(G^w) = r⁺_d(G) + 1

Subgraph Monotonicity (Lemma 3.2):

H ⊆ G ⟹ r⁺_d(H) ≥ r⁺_d(G)

3. Rank Contribution Analysis

Definition: For random vertex ordering π, rank contribution of vertex v:

rc_d(G, v, π) = r_d(G[T^π_v ∪ {v}]) - r_d(G[T^π_v])
rc_d(G, v) = E(rc_d(G, v, π))

Fundamental Equation (Lemma 3.6):

r_d(G) = Σ_{v∈V} rc_d(G, v)

Lower Bound rc*_d(G,v) (Lemma 3.7):

rc*_d(G, v) ≤ rc_d(G, v)

where rc*_d is defined through contraction of non-adjacent edges, easier to compute

Key Estimate (Lemma 3.9): If r_d(G) ≥ r_d(G-v) + d + t, then

rc*_d(G, v) ≥ d + [t(deg(v) - d + 1) - d(d+1)] / [2(deg(v) + 1)]

Main Theorem Proof Strategies

Proof of Theorem 1.2 (f(n,d) ≤ n/2 + d - 1)

Proof Outline: Induction on d

1. Base Case: d=1 follows directly from connectivity lemma
2. Inductive Step: Assume counterexample G exists
   • G is R^d-closed (otherwise can add edges)
   • n ≥ 2d+2 (from degree condition)
   • Exists vertex u with deg(u) = n/2 + d - 1 (otherwise can delete vertex and maintain condition)
3. Construct Critical Vertex Pair:
   • Let X = V - N(u) - {u}, |X| = n/2 - d
   • Exists v such that |N(v) ∩ X| ≥ (|X|+1)/2
   • Let U = N(u) ∪ N(v) - {u,v}
4. Degree Analysis (Claim 3.5): Prove |V - U| ≥ d + 2
   • Contract {u,v} to get G'
   • G' is not rigid but H = G' - w is rigid in R^{d-1} (by inductive hypothesis)
   • Use Lemma 2.6 and 3.4 to derive contradiction
5. Final Contradiction:
   • Apply Lemma 3.3 to get r⁺_{2d-1}(G-v) ≥ 4d-2
   • Contradicts Lemma 3.4

Proof of Theorem 1.3 (f(n,d) = ⌈(n+d-2)/2⌉ for n ≥ 29d)

Proof Strategy: Induction on d, proof by contradiction

1. Degree Bound (Claim 3.12): n ≤ d(d+1) - 1
   • Otherwise use Lemma 3.11 (based on rigidity of G' = G + K(N(v)))
   • Rank contribution summation yields r_d(G) ≥ nd - (d+1 choose 2)
2. Maximum Degree Restriction (Claim 3.13): Δ(G) ≤ n - 3d - 1
   • Assume Δ(G) = n - l, l ≥ 2
   • Add edges to make xz an R^{d+l-2}-bridge
   • Apply Lemma 3.3 and 3.4 to derive contradiction
3. Dimension Lifting Technique:
   • Let s = ⌈9d/20⌉, d' = d + s
   • Prove r⁺_{d'}(G) ≥ d' + 2s - 1 (Claim 3.14)
   • Use refined estimates from Lemma 3.3
4. Rank Contribution Lower Bound (Claim 3.15):

   Σ_{v∈V} p(N(v)) ≥ n(d' + s/3 - 1)
   

   
   where p(U) = r_{d'}(G^{w,U}) - r_{d'}(G)
5. Synthesis:
   • Combine Lemma 3.9 and Claim 3.15
   • Obtain r_{d'}(G) ≥ nd' - (d'+1 choose 2)
   • Contradicts non-rigidity of G

Proof of Theorem 5.1 (Complete Characterization for d=3)

Main Result: If η(G) ≥ n+1 and G ∉ {W₅, B₆, C¹₇, C²₇}, then G is rigid in R³

Proof Framework:

1. Small Graph Cases (Lemmas 5.5-5.7):
   • 6 ≤ n ≤ 7: Direct verification
   • 8 ≤ n ≤ 10: Constructive proof of K₄ subgraph existence
   • n ≥ 5, δ=3: All except W₅ and B₆ are rigid
2. Inductive Hypothesis: G is minimal counterexample, R³-closed
3. Structural Analysis:
   • Let C be maximum complete subgraph, D = V - C, H = GD
   • Claim 5.8: q = |C| ≥ 4 (using Lemma 3.10 rank contribution estimate)
   • Claim 5.9: q ≤ (n-1)/2 and H is not rigid
   • Claim 5.10: H ∉ {W₅, B₆, C¹₇, C²₇}
4. Recursive Application: H satisfies η(H) ≥ |D|+1, so by inductive hypothesis H is rigid, contradiction
5. Exceptional Graph Verification: Direct calculation shows W₅, B₆, C¹₇, C²₇ have edge count < 3n-6

Experimental Setup

This is a pure theoretical mathematics paper with no traditional experiments. All results are established through rigorous mathematical proofs.

Theoretical Verification Methods

1. Constructive Proofs: Through graph operations (0-extension, 1-extension, vertex splitting) preserving rigidity
2. Proof by Contradiction: Assume minimal counterexample and derive contradiction
3. Mathematical Induction: On dimension d or vertex count n
4. Matroid Arguments: Using submodularity and monotonicity of rank functions
5. Probabilistic Method: Expectation analysis of rank contributions

Key Lemma Verification

• Lemma 2.1-2.7: Fundamental graph theory and matroid properties
• Lemma 3.1-3.4: Properties of new parameter r⁺_d, verified through direct computation and inequalities
• Lemma 3.6-3.11: Probabilistic estimates of rank contributions, based on linearity of expectation and Hoeffding inequality
• Lemma 5.5-5.7: Exhaustive verification of small graphs

Experimental Results

Summary of Main Theorems

1. Minimum Degree Conditions (Question 1)

Key Improvements:

• Removed restriction n ≥ Ω(d) log² n from 12
• Exact threshold improved from n ≥ d(2d+1)+2 to n ≥ 29d

2. Degree Sum Conditions (Question 2)

Conjecture 1.5 Verification: For n > 2d+2, conjecture g(n,d) = n+d-2 holds in:

• n ≥ d(d+2) (Theorem 1.7)
• d = 2, 3 (Theorems 5.1, 5.3)

3. Random Graph Application (Theorem 1.8)

Main Result: G(n,1/2) is almost surely rigid in R^d where

d = 7n/32 - √(15n log n)/16

Historical Comparison:

• Previous best: d = Ω(n/log n) 11
• This paper: d ~ 0.21875n (first linear lower bound)
• Conjectured upper bound: d ~ 0.2928n (from Conjecture 6.1)

Proof Technique:

• Through n/2 vertex pair contractions, final graph G_{n/2} ~ G(n/2, 15/16)
• Prove each contraction realizable as spider splitting (preserving rigidity)
• Key: prove common neighbor count ≥ d using Hoeffding inequality

4. Exact Values in Low Dimensions

Complete Results for d=3 (Corollary 5.2):

g(n,3) = {
  n+2,  if n ∈ {5,6,7}
  n+1,  otherwise
}

f(n,3) = max{⌈(n+1)/2⌉, ⌈6 - 12/n⌉}

Complete Results for d=2 (Corollary 5.4):

g(n,2) = {
  n+1,  if n = 4
  n,    otherwise
}

f(n,2) = max{⌈n/2⌉, ⌈4 - 6/n⌉}

Theoretical Findings

1. Relationship between f(n,d) and g(n,d):
   • For all known cases, f(n,d) = ⌈g(n,d)/2⌉ holds exactly
   • Supports conjecture: this relationship holds for all n,d
2. Dimension Lifting Technique:
   • Prove rigidity in higher dimension (d+s) to deduce d-dimensional rigidity
   • Choice s = ⌈9d/20⌉ balances different estimates
3. Structure of Exceptional Graphs:
   • Appear only for small n (n ≤ 7)
   • All are highly symmetric graphs
   • Edge count exactly 1 less than rigidity threshold
4. Global Rigidity Corollaries (Section 7.2):
   • R^d rigidity ⟹ R^{d-1} global rigidity (Theorem 7.2)
   • All minimum degree/degree sum conditions automatically yield global rigidity results

Related Work

Rigidity Theory Foundations

1. Classical Results:
   • Laman's Theorem (1970): Combinatorial characterization of R² rigidity
   • Whiteley's Coning Theorem (1983): Dimension lifting technique
   • Vertex Splitting Theorem (1990): Graph operations preserving rigidity
2. Connectivity Conditions:
   • 17 Villányi (2025): d(d+1)-connectivity ⟹ d-rigidity
   • This paper improves: minimum degree conditions are much weaker

Degree Condition Research

3. Global Rigidity:
   • 1 Berger-Kleinberg-Leighton (1999): Sensor network applications
   • 3 Jackson-Jordán (2009): δ(G) ≥ (n+1)/2 ⟹ R² global rigidity
   • This paper: generalization to arbitrary dimensions
4. Matrix Completion:
   • 5 Jackson-Jordán-Tanigawa (2016): Low-rank matrix completion
   • Deep connections with rigidity theory

Recent Progress

5. Krivelevich-Lew-Michaeli Series:
   • 11 (2025): f(n,d) ≤ (n + 3d log n)/2
   • 12 (2024): f(n,d) ≤ n/2 + d - 1 (n ≥ Ω(d) log² n)
   • Proposed Conjectures 1.1 and 1.4
   • This paper completely resolves these conjectures
6. Random Graph Rigidity:
   • 7 Jackson-Servatius-Servatius (2007): Threshold for d=2
   • 13 Lew-Nevo-Peled-Raz (2023): Exact hitting time for fixed d
   • 15 Peled-Peleg (2024): Case p = o(n^{-1/2})
   • This paper: first linear lower bound for G(n,1/2)

Advantages of This Paper

1. Removes Log Factor: Pure combinatorial proof without logarithmic loss from probabilistic techniques
2. Exact Thresholds: Achieves theoretical lower bound when n ≥ 29d
3. Complete Characterization: All n cases for d=2,3
4. Method Innovation: r⁺_d parameter and rank contribution techniques
5. Application Breakthrough: First linear dimension bound for random graphs

Conclusions and Discussion

Main Conclusions

1. Complete Resolution of Conjecture 1.1: Proof that K=1 for all n,d, the best possible constant
2. Exact Threshold: For n ≥ 29d, f(n,d) achieves theoretical lower bound ⌈(n+d-2)/2⌉
3. Degree Sum Conditions:
   • General upper bound g(n,d) ≤ n + 3d - 3
   • Exact value g(n,d) = n + d - 2 for large n
   • Complete determination for d=2,3
4. Random Graph Breakthrough: G(n,1/2) is rigid in R^d where d ~ 0.22n, answering Peled-Peleg question
5. Methodological Contributions:
   • New parameter r⁺_d provides matroid analysis tools
   • Probabilistic techniques for rank contributions systematized
   • Pure combinatorial methods replace some probabilistic arguments

Limitations

1. Gap Regions:
   • Exact values of f(n,d) unknown for d < n < 29d
   • Combined bounds (1) and (2) not always tight
2. Conjecture 1.5:
   • Conjecture g(n,d) = n+d-2 for n > 2d+2
   • Proven only for n ≥ d(d+2) or d ≤ 3
   • Gap in 2d+2 < n < d(d+2)
3. Random Graphs:
   • Optimal dimension for G(n,1/2) has ~30% gap (0.22 vs 0.29)
   • Conjecture 6.1 unresolved for general p
   • Sparse case (p = ω(log n/n)) techniques inapplicable
4. Exceptional Graphs:
   • Unknown if similar exceptions to W₅ exist for d ≥ 4
   • Complete characterization for small n difficult
5. Computational Complexity:
   • Paper does not discuss algorithm efficiency for d-rigidity testing
   • Computational challenges in practical applications

Future Directions

1. Theoretical Questions:
   • Complete resolution of Conjecture 1.5 (all n > 2d+2)
   • Exact formula for f(n,d) when d < n < 29d
   • Generalization to other rigidity models (body-bar, body-hinge, etc.)
2. Random Graphs:
   • Close gap in dimension bounds for G(n,1/2)
   • Prove or disprove Conjecture 6.1
   • Study exact thresholds for other densities p
3. High-Dimensional Generalization:
   • Complete characterization for d ≥ 4
   • Systematic classification of exceptional graphs
   • Finer structural theorems
4. Algorithmic Applications:
   • Efficient rigidity testing algorithms
   • Sensor network localization
   • Structural stability analysis
5. Related Problems:
   • Independent conditions for global rigidity (not via Theorem 7.2)
   • Sufficient conditions using other graph parameters (treewidth, chromatic number, etc.)
   • Generalizations to weighted and directed graphs

In-Depth Evaluation

Strengths

1. Theoretical Depth

• Complete Resolution of Open Problems: Proofs of Conjectures 1.1 and 1.4 (d=2,3) fill gaps in the field
• Optimal Results: Multiple theorems achieve information-theoretic lower bounds, cannot be improved
• Unified Framework: r⁺_d parameter elegantly unifies analysis across dimensions

2. Technical Innovation

• New Tools: r⁺_d parameter is original contribution to matroid analysis with broad applicability
• Method Diversity: Combines matroid theory, graph theory, probabilistic methods, and combinatorial optimization
• Refined Estimates: Inequalities in Lemmas 3.3-3.4 achieve sharp bounds

3. Proof Quality

• Rigor: All proofs logically clear with complete steps
• Readability: Progression from simple to complex cases, well-organized
• Modularity: Strong independence of lemmas, facilitates citation and generalization

4. Application Value

• Random Graph Breakthrough: First linear lower bound has significance for probabilistic combinatorics
• Practical Relevance: Theoretical foundation for sensor networks and structural engineering
• Global Rigidity: Section 7 corollaries automatically resolve related problems

5. Writing Quality

• Clear Organization: Logical flow from motivation to applications
• Complete Background: Section 2 preliminaries are self-contained
• Visual Aids: Figure 1 exceptional graphs illustrated intuitively

Weaknesses

1. Technical Limitations

• Unresolved Gaps: Cases d < n < 29d and 2d+2 < n < d(d+2) remain open
• Constant 29d: Choice s = ⌈9d/20⌉ appears suboptimal, possibly improvable to smaller constant
• Systematic Approach for d ≥ 4 Missing: Lack systematic method for exceptional graphs when d ≥ 4

2. Method Limitations

• Induction Dependency: Most proofs require induction on d, difficult to generalize to all d directly
• Proof by Contradiction Complexity: Minimal counterexample analysis involves extensive case discussion
• Probabilistic Technique Limits: Rank contribution method has limited effectiveness for sparse graphs

3. Presentation Issues

• Computational Details: Some inequalities (e.g., Claim 3.14) omit intermediate steps
• Exceptional Graph Verification: Non-rigidity of W₅ etc. merely stated as "easily verified" without detailed calculation
• Random Graph Proof: Theorem 1.8 proof relatively brief, could be more detailed

4. Application Discussion

• Algorithm Aspects: No discussion of computational complexity for rigidity testing
• Practical Data: Lacks case studies on real networks
• Other Models: Connections to body-bar and other rigidity models not explored

5. Open Problems

• Conjecture 1.5: While partially resolved, complete proof remains elusive
• Conjecture 6.1: Optimal dimension bound for random graphs not achieved
• Asymptotic Behavior: Limiting behavior as d → ∞ not analyzed

Impact Assessment

Contribution to Field

1. Theoretical Breakthrough:
   • Resolves two major conjectures by Krivelevich et al.
   • Establishes precise connection between degree conditions and rigidity
   • Provides new tools (r⁺_d parameter) for future research
2. Methodological Impact:
   • Rank contribution techniques generalizable to other matroid problems
   • Dimension lifting tricks applicable to broader geometric problems
   • Probabilistic-combinatorial synthesis becomes paradigm
3. Interdisciplinary Connections:
   • Links graph theory, matroid theory, probability, and discrete geometry
   • Provides theoretical foundation for sensor networks and structural engineering
   • Inspires related fields like matrix completion

Practical Value

1. Sensor Network Localization:
   • Provides sufficient conditions for network connectivity
   • Guides design of sparse networks
2. Structural Engineering:
   • Quick criteria for framework stability
   • Optimizes material usage (minimum edges)
3. Algorithm Design:
   • While no algorithms provided, theory enables efficient algorithm development
   • Random graph results guide randomization strategies

Reproducibility

1. Theoretical Results:
   • All theorems have complete proofs, independently verifiable
   • Clear lemma dependencies
2. Technical Details:
   • Key inequalities can be re-derived
   • Exceptional graphs verifiable computationally
3. Generalization Potential:
   • Methods applicable to other graph classes
   • Techniques extendable to related problems

Applicable Scenarios

1. Theoretical Research:
   • Further development of rigidity theory
   • Matroid theory applications
   • Extremal graph theory problems
2. Application Domains:
   • Wireless sensor network design
   • Robot formation control
   • Molecular structure analysis
   • Building frame design
3. Teaching Use:
   • Advanced cases in combinatorial optimization courses
   • Matroid theory application examples
   • Probabilistic method demonstrations
4. Software Development:
   • Rigidity testing algorithm implementation
   • Network topology optimization tools
   • Structural analysis software

Overall Evaluation

This is a high-quality theoretical mathematics paper making substantial contributions to rigidity theory. Main strengths:

1. Resolves Important Conjectures: Complete answers to core field questions
2. Technical Innovation: New tools with broad applicability
3. Optimal Results: Multiple theorems achieve information-theoretic bounds
4. Rigorous Proofs: Complete logic with deep techniques

Main weaknesses:

1. Partial Gaps: Exact values unknown for certain parameter ranges
2. Computational Aspects: Lacks algorithm and complexity analysis
3. Application Discussion: Insufficient real-world case studies

Recommendation Score: ★★★★★ (5/5)

Target Audience:

• Combinatorial optimization researchers
• Matroid theory scholars
• Graph theory and network science practitioners
• Sensor network engineers

Expected Impact:

• Short-term: Becomes standard reference in rigidity theory
• Medium-term: Inspires research on related problems (global rigidity, other models)
• Long-term: Methodological contributions (r⁺_d parameter, rank contribution techniques) widely applied

References

The paper cites 23 references, key ones include:

1. 11 Krivelevich, Lew, Michaeli (2025): Proposed Conjecture 1.1, established f(n,d) ≤ (n+3d log n)/2
2. 12 Krivelevich, Lew, Michaeli (2024): Improved to f(n,d) ≤ n/2+d-1 (large n), proposed Conjecture 1.4
3. 17 Villányi (2025): d(d+1)-connectivity sufficient condition, probabilistic method foundation
4. 18 Whiteley (1983): Coning theorem, theoretical basis for dimension lifting
5. 19 Whiteley (1990): Vertex splitting theorem, graph operations preserving rigidity
6. 15 Peled-Peleg (2024): Random graph rigidity, posed G(n,1/2) question
7. 13 Lew-Nevo-Peled-Raz (2023): Exact thresholds for fixed dimension
8. 6 Jackson-Jordán-Villányi: Rank contribution method development (manuscript)

These references form the theoretical foundation and direct motivation for this work.