TOPICS
Search

Vertex Splitting


Vertex splitting is an operation on a finite simple graph that replaces a graph vertex w by two adjacent vertices u and v and redistributes the edges formerly incident to w. Each former neighbor of w is joined to at least one of u and v, and may be joined to both. All other edges are unchanged. Thus edge contraction of uv, with loops removed and parallel edges identified, recovers the original graph. This is an inverse contraction of the kind called edge splitting in this work. Other uses of that name describe a different operation (Schulze and Whiteley 2017, pp. 1597-1599).

In rigidity theory, for a positive integer d, a d-dimensional vertex split has exactly d-1 common neighbors of the two new vertices. Whiteley (1990) proved that this operation preserves generic rigidity in R^d. A split is nontrivial when both new vertex degrees are at least d+1.

Cruickshank (2026) reports a proof that, for every integer d>=1, a nontrivial d-dimensional vertex split of a generically globally rigid graph in R^d is again generically globally rigid. In contraction notation, if H=G/uv is generically globally rigid, deg_G(u)>=d+1, deg_G(v)>=d+1, and |N_G(u) intersection N_G(v)|=d-1, then G is generically globally rigid. A corollary allows at least d-1 common neighbors. The proof establishes the stronger assertion that duplicating the position of the contracted graph vertex in any generic realization of H gives an infinitesimally rigid framework of G with u and v coincident. The two velocity vectors are allowed to differ when testing infinitesimal rigidity.

Cruickshank credits ChatGPT 6.1 Sol with discovering the new proofs and reports checking the arguments. Independent specialist verification or formal certification of the complete proofs has not been reported.


See also

Edge Contraction, Edge Splitting, Generically Globally Rigid, Rigid Graph

Explore with Wolfram|Alpha

References

Cruickshank, J. "Vertex Splitting, Global Rigidity and Nondegenerate Equilibrium Stresses." 7 Nov 2026. https://arxiv.org/abs/2611.10919v1.Schulze, B. and Whiteley, W. "Rigidity and Scene Analysis." In Handbook of Discrete and Computational Geometry, 3rd ed. (Ed. C. D. Tóth, J. O'Rourke, and J. E. Goodman). Boca Raton, FL: CRC Press, pp. 1593-1632, 2017. https://www.csun.edu/~ctoth/Handbook/chap61.pdf.Whiteley, W. "Vertex Splitting in Isostatic Frameworks." Structural Topology 16, 23-30, 1990. https://upcommons.upc.edu/entities/publication/38dd0d73-0bf7-4092-ab1f-919edb98e440.

Cite this as:

Weisstein, Eric W. "Vertex Splitting." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/VertexSplitting.html

Subject classifications