A NOTE ON THE NUMBER OF PERFECT MATCHINGS OF BIPARTITE GRAPHS

Let G be a bipartite graph with 2n vertices, A its adjacency matrix an d K the number of perfect matchings. For plane bipartite graphs each i nterior face of which is surrounded by a circuit of length 4s+2, s is an element of {1,2,...}, an elegant formula, i.e. detA = (-1)K-n(2), h ad been rigorously proved by Cvetkovic et al. (1982). For general bipa rtite graphs, this note contains a necessary and sufficient condition for the above relation to hold. A fast algorithm to check if a plane b ipartite graph has such a relation is given.