A Note on Divisibility of the Number of Matchings of a Family of Graphs

Kyung-Won Hwang, Naeem N. Sheikh, Stephen G. Hartke


For a certain graph obtained by adding extra vertices and edges to the triangular lattice graph, Propp conjectured that the number of perfect matchings of such a graph is always divisible by $3$. In this note we prove this conjecture.

Full Text: PDF