In this paper, we study a new construction which associates a combinatorial cubical complex \(\texttt {Flex}(G)\) to an arbitrary undirected simple graph G. The vertices of \(\texttt {Flex}(G)\) are indexed by all possible orientations of the edges of G. The cells of \(\texttt {Flex}(G)\) are the sets of independent flexes, where a flex is a simultaneous change of orientations of the edges adjacent to a certain sink or a certain source in G. Accordingly, we call \(\texttt {Flex}(G)\) the flex complex of the graph G. Our focus is on studying topology and combinatorics of the flex complexes. The main topological theorem says that for an arbitrary graph G, the flex complex \(\texttt {Flex}(G)\) is homotopy equivalent to a disjoint union of tori. We also provide formulae for the number of these tori. Furthermore, we prove a much more precise combinatorial result saying that when G is connected, every connected component of \(\texttt {Flex}(G)\) is either a collapsible cubical complex, or can be collapsed to a cycle whose length is equal to the number of vertices of G. We shall provide a combinatorial enumeration for the components of both types. Our study is motivated by the beauty and naturality of the graph construction, as well as by the mathematical modeling of the network evolution.
