Perfect matchings in the triangular lattice Original Research Article

Let V be a finite subset of vertices of the infinite planar triangular lattice T, and G denote the subgraph induced by V. We assume that G is simply connected (i.e. G and the subgraph induced by T − V are both connected). Firstly, we prove that if the vertex-connectivity of G is at least 2, and V is even, then G has a perfect matching. Secondly, we devise a linear-time algorithm for finding a perfect matching of G when it exists. Thirdly, we prove that any perfect matching of G can be transformed into any other perfect matching of G by a linear number of local transformations involving at most 4 edges.