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

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

Abstract

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.

Published
2009-03-20
Article Number
N10