On the Existence of a Perfect Matching for 4-regular Graphs derived from Quadrilateral Meshes
Carlos D. Carbonera, Jason F. Shepherd · SIAM Journal on Discrete Mathematics · 2006
In 1891, Peterson [Pet91] proved that every 3-regular bridgeless graph has a perfect matching. It is well-known that the dual of a triangular mesh on a compact manifolds is a 3-regular graph. M. Gopi and D. Eppstein [GE04] use Petersons theorem to solve the problem of constructing strips of triangles from triangular meshes on a compact manifold. P. Diaz-Gutierrez and M. Gopi [DG04] elaborate on the creation of strips of quadrilaterals when a perfect matching exists. In this paper, it is shown that the dual of a quadrilateral mesh on a 2-dimensional compact manifold with an even number of quadrilaterals (which is a 4-regular graph) also has a perfect matching. In general, however, not all 4-regular graphs have a perfect matching. Indeed, a counter-example is given that is planar.