Braces and Rigidity

Suppose that we construct structures with rods joined end to end. We say that these structures are rigid if they don't warp or contort under stress. For example, the structure below:

Is not rigid, as the structure can be warped under stress. This problem can be fixed with the addition of braces however:

The addition braces does not always make a structure rigid though. For example, the follow structure is not rigid because it can be bent:

In general, we can imagine whether or not a structure is rigid or not if we imagine the squares with braces as metal plate and the squares without braces as pieces of paper. If the structure bends while holding it, then it is not rigid.

Determining if a Structure is Rigid

We will now define a rigid structure in terms of graphs.

Definition: A structure is considered Rigid if and only if the bipartite graph that represents the structure is connected.

To construct a bipartite graph of an $m \times n$ sized structure, let $r_1, r_2, ..., r_m$ be the set of vertices corresponding to the $m$ rows in the structure, and let $c_1, c_2, ..., c_m$ be the set of vertices corresponding to the $n$ columns in the structure. We will put an edge between vertices if a brace is present. For example, the following structure is rigid, since the associated bipartite graph is connected. If this bipartite graph was not connected, then the structure would not be considered rigid.