Perfect matchings in the triangular lattice (Q1917494)

There are three infinite \(s\)-angular regular planar lattices \(L\) (\(s= 3, 4\) and 6). Let \(G\) be an induced subgraph on a finite set \(V\) of vertices of \(L\) such that both \(G\) and \(L- V\) are connected. This paper complements \textit{W. P. Thurston's} work (see Am. Math. Mon. 97, No. 8, 757-773 (1990; Zbl 0714.52007)). The main results concern \(s= 3\): If \(G\) is 2-vertex-connected and of even order then it has a perfect matching. A linear-time algorithm for finding a perfect matching is devised. Also considerations from the viewpoint of tiling are given.