Origami-based mechanical metamaterials have recently received significant scientific interest due to their versatile and reconfigurable architectures. However, it is often challenging to account for all possible geometrical configurations of the origami assembly when each origami cell can take multiple phases. Here, we investigate the reconfigurability of a tessellation of origami-based cellular structures composed of bellows-like unit cells, specifically Tachi-Miura Polyhedron (TMP). One of the unique features of the TMP is that a single cell can take four different phases in a rigid foldable manner. Therefore, the TMP tessellation can achieve various shapes out of one original assembly. To assess the geometrical validity of the astronomical number of origami phase combinations, we build a graph-theoretic framework to describe the connectivity of unit cells and to analyze the reconfigurability of the tessellations. Our approach can pave the way to develop a systematic computational tool to design origami-based mechanical metamaterials with tailored properties.