The Cartesian product Cm X Pn of a cycle Cm and a path Pn, n ~ 2, is called a prism. It can be checked from  that points in the Euclidean space R 3 can be chosen to represent the vertices of the prism such that the distance between points representing adjacent vertices is 1. Thus, Cm X Pn is a so called unit graph in R 3 . Clearly, this graph is flexible(not rigid) in R 3 . We can flex the prism so that the distance between some non-adjacent vertices will be equal to 1. Then, a new unit edge can be added to join such a pair of vertices. This paper will show how to do such addition of edges, using only the minimum number of edges, to transform the prism to a rigid unit graph in R 3 .
On Minimal Rigidity of Prisms (225.2 KiB)