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

摘要

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