Rigidity of convex polyhedrons in $\mathbb R^3$ with faces removed Take a convex polyhedron $P$ in $\mathbb R^3$ and remove all the faces, i.e. leave only the edges. Call this graph $E$. Let us now try to continuously deform $E$ in $\mathbb R^3$ so that all the edges of $E$ keep their length and remain straight (like metal sticks), but allow the change of angles between the edges.
Question. Is it true that $E$ admits non-trivial deformations (not globally isomteric) if at least one face of $P$ is not a triangle?
Note that if all the faces of $P$ are triangles it is not deformable by Cauchy's rigidity theorem: https://en.wikipedia.org/wiki/Cauchy%27s_theorem_(geometry)
 A: I am not seeing the nontrivial deformation of the $E$ below,
a triangulation of a cube except for the top face.
Can someone explain? Thanks!

          


Update. The deformation of
this cardboard model is essentially what Nik Weaver described in a comment.

          


A: Let me show how to reduce the problem to Alexandrov existence theorem; that is, the original idea of j.c. works.
Let us modify the polyhedron by adding a low pyramid over each non-triangular face. The edges which we add this way will be called new.  
This graph is rigid by Cauchy theorem. Moreover if we slightly change the length of a new edge, then by Alexandrov existence we get one parameter family of rigid graphs.
Evidently the old part of graph moves, hence we get the required deformation.
A: As Anton's answer suggests, it is not possible to isometrically flex the edge graph while keeping all the coplanar edges in the same plane. This follows quickly from Cauchy's proof of his rigidity theorem. Indeed if all the faces remain flat, then we can compare the dihedral angles around each vertex of the new polyhedron $P'$ with those of the original polyhedron $P$. By Cauchy's lemma there must be at least 4 sign changes around each vertex, if there are any sign changes at all, when we consider the difference between the corresponding dihedral angles of $P$ and $P'$. So it follows from Euler's formula that all dihedral angles must be equal. It remains only to observe that if two combinatorially isomorphic convex polyhedra have equal edge lengths and dihedral angles then they are congruent.
In short the answer would have been No if there had been an additional requirement to preserve the combinatorial structure of the polyhedron.
A: Yes, this is true. 
One strategy is to use the naïve approach of counting degrees of freedom and constraints.  For triangulated polyhedra one can easily show with the Euler characteristic that the expected dimension (number of variables minus number of equations) of the realization space modulo Euclidean isometries is zero, and Cauchy would then imply that this is the case for a convex embedding.  Then we can get to any polyhedron with a nontriangular face by removing some number of edges from a triangulated one and thus the dimension of the realization space is positive.  However, this alone doesn't guarantee that the set of real points is positive dimensional.   This point is made in Pak's lectures, e.g. Remark 26.3 and footnote 55 on page 248.
To deal with this issue, we appeal to a theorem of Asimow and Roth (Section 3 of "The rigidity of graphs", L. Asimow and B. Roth, Trans. Amer. Math. Soc. 245 (1978), 279-289).  
This theorem states: Let $G$ be a graph with $v$ vertices, $e$ edges and let $p\in\mathbb{R}^{nv}$ be a regular point of the length-squared function $f_G:\mathbb{R}^{nv}\rightarrow \mathbb{R}^e$ (which maps a point in $\mathbb{R}^{nv}$, to the vector of squared-edge lengths). Suppose that the affine span of $p$ viewed as a configuration of $v$ points in $\mathbb{R}^n$ is all of $\mathbb{R}^n$. Then $(G,p)$ is (locally) rigid (every $q$ sufficiently close to $p$ with $f_G(q)=f_G(p)$ is induced by an isometry of $\mathbb{R}^n$) if and only if the rank of $df_G(p)=nv-n(n+1)/2$.
Now let $P'$ be a triangulation of your polyhedron $P$ and let $E'$ be the 1-skeleton of $P'$. Suppose that $E$ (and hence $E'$) both have $v$ vertices with placement $p\in\mathbb{R}^{3v}$. Since $E'$ is the graph of a triangulated polyhedron, $E'$ has $e'=3v-6$ edges and by assumption $E$ has $e<3v-6$ edges. Cauchy's rigidity theorem guarantees that $E'$ is rigid, hence the rank of $df_{E'}(p)=3v-6=e'$.  Note that the matrix for $df_{E}(p)$ consists of a strict subset of rows of $df_{E'}(p)$ and so by basic linear algebra its rank is $e<3v-6$. Asimow-Roth thus implies that $(E,p)$ cannot be rigid.

Ivan Izmestiev has pointed out the following doesn't work: see the comments.
This follows from Theorem 30.1 (section 30.9, page 283) in Igor Pak's lecture notes, which is proved in section 37.3 (page 332).  To see this, consider any triangulation $P'$ of $P$. Then let $F_1,F_2$ be a pair of adjacent triangles in $P'$ which are part of a triangulation of a non-triangular face of $P$. Theorem 30.1 implies that $P''=P'\setminus (F_1\cup F_2)$ is a flexible polyhedral surface, and the flexes of $P''$ give rise to a desired flex of $E$, the 1-skeleton of $P$.
The proof relies on the Alexandrov existence theorem, which states that "every intrinsically convex 2-dimensional surface homeomorphic to a sphere is isometric to the surface of a convex polytope in $\mathbb{R}^3$ or a doubly covered polygon".
A: I would like to share one picture which shows how flexibility of polyhedrons with faces removed can be tested. This is an illustration for the polytope proposed by Joseph:

The whole construction is made of plastic tubes that are hold by rubber bands.
